1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from collections import defaultdict

n = int(input())

Graph = defaultdict(list)
idx = [0] * n

val = [0] * n
used = [0] * n
nr = 0

def update(cnt):
    val[0] = cnt
    for i in range(n - 1):
        val[i + 1] = 0

    global nr
    nr += 1
    
    for i in range(n):
        if val[i] == 0 or len(Graph[i]) == 0:
            continue
        
        if used[i] == nr:
            continue
        used[i] = nr

        num = 0
        val_split = val[i] // len(Graph[i])

        for j in range(len(Graph[i]) - idx[i]):
            num += 1
            val[Graph[i][j + idx[i]]] += val_split

            if num <= (val[i] % len(Graph[i])):
                val[Graph[i][j + idx[i]]] += 1

        for j in range(idx[i]):
            num += 1
            val[Graph[i][j]] += val_split

            if num <= (val[i] % len(Graph[i])):
                val[Graph[i][j]] += 1

        idx[i] += val[i]
        idx[i] %= max(1, len(Graph[i]))

def GCD(a, b):
    if b == 0:
        return a
    return GCD(b, a % b)

def LCM(a, b):
    return (a * b) // GCD(a, b)

for i in range(n):
    inp = [int(j) for j in input().split()]

    for j in range(inp[0]):
        Graph[i].append(inp[j + 1] - 1)

ans = len(Graph[0])
update(ans)

for i in range(n - 1):
    if idx[i + 1] != 0:
        needed = (LCM(idx[i + 1], len(Graph[i + 1])) // idx[i + 1]) * ans
        update(needed - ans)
        ans = needed

print(max(1, ans))