---

1574
личный сертификат


```
import random
from collections import Counter

n, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(K)]

if K == 1:
    print("YES")
    raise SystemExit

if len(set(map(tuple, P))) < K:
    print("NO")
    raise SystemExit

lo_n = min(n, 8)
hi_n = n - lo_n
LO = []
HI = []
for p in P:
    lo = [0] * (1 << lo_n)
    for s in range(1, 1 << lo_n):
        b = (s & -s).bit_length() - 1
        lo[s] = lo[s & (s - 1)] | (1 << (p[b] - 1))
    hi = [0] * (1 << hi_n)
    for s in range(1, 1 << hi_n):
        b = (s & -s).bit_length() - 1
        hi[s] = hi[s & (s - 1)] | (1 << (p[lo_n + b] - 1))
    LO.append(lo)
    HI.append(hi)

ok = [False] * K
mlo = (1 << lo_n) - 1
total = 1 << n
rng = range(K)
for _ in range(400):
    S = random.randrange(total)
    a = S & mlo
    b = S >> lo_n
    vals = [LO[j][a] | HI[j][b] for j in rng]
    cnt = Counter(vals)
    for j in rng:
        if cnt[vals[j]] == 1:
            ok[j] = True
    if all(ok):
        break

inv = []
for p in P:
    q = [0] * n
    for x in range(n):
        q[p[x] - 1] = x
    inv.append(q)

full = (1 << total) - 1
cache = {}

for i in rng:
    if ok[i]:
        continue
    pi = P[i]
    U = 0
    for j in rng:
        if j == i:
            continue
        ij = inv[j]
        sigma = [ij[pi[x] - 1] for x in range(n)]
        seen = 0
        masks = []
        for x in range(n):
            if seen >> x & 1:
                continue
            m = 0
            y = x
            while not (m >> y & 1):
                m |= 1 << y
                y = sigma[y]
            seen |= m
            masks.append(m)
        masks.sort()
        key = tuple(masks)
        L = cache.get(key)
        if L is None:
            L = 1
            for m in masks:
                L |= L << m
            cache[key] = L
        U |= L
        if U == full:
            break
    if U == full:
        print("NO")
        raise SystemExit

print("YES")
```