Chat Screenshots (Codeforces 1931F)
Tags: Others, graphs

There are $$$n$$$ people in the programming contest chat. Chat participants are ordered by activity, but each person sees himself at the top of the list.For example, there are $$$4$$$ participants in the chat, and their order is $$$[2, 3, 1, 4]$$$. Then   $$$1$$$-st user sees the order $$$[1, 2, 3, 4]$$$.  $$$2$$$-nd user sees the order $$$[2, 3, 1, 4]$$$.  $$$3$$$-rd user sees the order $$$[3, 2, 1, 4]$$$.  $$$4$$$-th user sees the order $$$[4, 2, 3, 1]$$$. $$$k$$$ people posted screenshots in the chat, which show the order of participants shown to this user. The screenshots were taken within a short period of time, and the order of participants has not changed. Your task is to determine whether there is a certain order that all screenshots correspond to.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of input test cases. The descriptions of test cases follow.The first line of the description of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5, n \cdot k \le 2 \cdot 10^5$$$) — the number of chat participants and the number of participants who posted screenshots.The following $$$k$$$ lines contain descriptions of screenshots posted by the participants.The $$$i$$$-th row contains $$$n$$$ integers $$$a_{ij}$$$ each ($$$1 \le a_{ij} \le n$$$, all $$$a_{ij}$$$ are different) — the order of participants shown to the participant $$$a_{i0}$$$, where $$$a_{i0}$$$ — the author of the screenshot. You can show that in the screenshot description it will always be at the top of the list.It is guaranteed that the sum of $$$n \cdot k$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed that all the authors of the screenshots are different.

Output: Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if there exists at least one order of participants, under which all $$$k$$$ screenshots could have been obtained. Otherwise, output "NO".You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.


Sample Inputs:
10
5 1
1 2 3 4 5
4 4
1 2 3 4
2 3 1 4
3 2 1 4
4 2 3 1
6 2
1 3 5 2 4 6
6 3 5 2 1 4
3 3
1 2 3
2 3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 1
1
5 2
1 2 3 5 4
2 1 3 5 4
3 3
3 1 2
2 3 1
1 3 2
5 4
3 5 1 4 2
2 5 1 4 3
1 5 4 3 2
5 1 4 3 2
3 3
1 3 2
2 1 3
3 2 1

Sample Outputs:
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO

Solution (Python):
from heapq import *
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    if m == 1:
        input()
        print('yes')
        continue
    (a1, *l1) = map(int, input().split())
    (a2, *l2) = map(int, input().split())
    l11 = [i for i in l1 if i != a2]
    l22 = [i for i in l2 if i != a1]
    if l11 != l22:
        for _ in range(m - 2):
            input()
        print('no')
        continue
    idx1 = idx2 = -1
    p1 = p2 = 0
    for i in range(n - 1):
        if i + max(p1, p2) == n - 1:
            break
        if l1[i + p1] != l2[i + p2]:
            if l1[i + p1] == a2 and l2[i + p2] == a1:
                idx1 = idx2 = i
                break
            else:
                if l1[i + p1] == a2:
                    idx1 = i
                    p1 = 1
                else:
                    idx2 = i
                    p2 = 1
                if idx1 >= 0 and idx2 >= 0:
                    break
    val = []
    if idx1 == -1 and idx2 != -1:
        idx1 = n - 2
    if idx2 == -1 and idx1 != -1:
        idx2 = n - 2
    if idx1 < idx2:
        l2.insert(idx1, a2)
        l = l2
    elif idx1 > idx2:
        l1.insert(idx2, a1)
        l = l1
    else:
        if m == 2:
            print('yes')
            continue
        (a3, *l3) = map(int, input().split())
        if l3.index(a1) < l3.index(a2):
            l1.insert(idx2, a1)
            l = l1
        else:
            l2.insert(idx1, a2)
            l = l2
        val.append((a3, l3))
        m -= 1
    for _ in range(m - 2):
        (a3, *l3) = map(int, input().split())
        val.append((a3, l3))
    for (a3, l3) in val:
        if l3 != [i for i in l if i != a3]:
            print('no')
            break
    else:
        print('yes')

Solution (Python):
ans = []
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    shot = [list(map(int, input().split())) for _ in range(k)]
    if n == 1 or k == 1:
        ans.append('YES')
        continue
    order = [-1] * (n + 1)
    x = shot[0][0]
    s = 1
    for i in range(1, n):
        order[shot[0][i]] = s
        s += 2
    done = True
    for i in range(1, k):
        if shot[i][1] == x and order[x] == -1:
            order[x] = 1
        for j in range(2, n):
            if shot[i][j] == x and order[x] == -1:
                order[x] = order[shot[i][j - 1]] + 2
            if order[shot[i][j - 1]] == order[shot[i][j]]:
                order[shot[i][j]] += 1
            if order[shot[i][j - 1]] > order[shot[i][j]]:
                done = False
                break
        if not done:
            break
    ans.append('YES' if done else 'NO')
for i in ans:
    print(i)

Solution (Python):
from collections import defaultdict

def compatible(pattern, x):
    pattern = pattern.copy()
    if x[0] in pattern:
        pattern.remove(x[0])
        return pattern == x[1:]
    return False

def solution(v):
    pairs = list()
    first_list = defaultdict(list)
    for x in v:
        first_list[x[0]].append(x)
    for (k, v) in first_list.items():
        for y in v:
            if y != v[0]:
                return False
    v = [v[0] for (k, v) in first_list.items()]
    if len(v) == 1:
        return True
    p = v[0] + [-1]
    q = v[1] + [-1]
    p_wants = p[0]
    q_wants = q[0]
    p_has = False
    q_has = False
    twice = False
    twice_pos = -1
    pi = 1
    qi = 1
    correct = list()
    while pi < len(p) and qi < len(q):
        if p[pi] == q[qi]:
            correct.append(p[pi])
            pi += 1
            qi += 1
        elif p[pi] == q_wants and q[qi] == p_wants:
            if q_has or p_has:
                return False
            twice_pos = len(correct)
            correct.append(p[pi])
            correct.append(q[qi])
            q_has = True
            p_has = True
            twice = True
            pi += 1
            qi += 1
        elif p[pi] == q_wants:
            q_has = True
            correct.append(p[pi])
            pi += 1
        elif q[qi] == p_wants:
            p_has = True
            correct.append(q[qi])
            qi += 1
        else:
            return False
    assert correct[-1] == -1
    correct.pop()
    if twice:
        c1 = correct
        c2 = correct.copy()
        (c2[twice_pos], c2[twice_pos + 1]) = (c2[twice_pos + 1], c2[twice_pos])
        correct = [c1, c2]
    else:
        correct = [correct]
    if len(correct) == 1:
        return all((compatible(correct[0], x) for x in v))
    else:
        return all((compatible(correct[0], x) for x in v)) or all((compatible(correct[1], x) for x in v))
t = int(input())
for _ in range(t):
    (n, k) = input().split()
    n = int(n)
    k = int(k)
    v = list()
    for _ in range(k):
        a = [int(x) for x in input().split()]
        v.append(a)
    if solution(v):
        print('YES')
    else:
        print('NO')