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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
from math import lcm, gcd

n = int(input())
graph = []
original_degs = []
froms = [[] for _ in range(n)]

for i in range(n):
    line = [i - 1 for i in map(int, input().split())]
    original_degs.append(line[0] + 1)
    graph.append(line[1:])
    for neigh in line[1:]:
        froms[neigh].append(i)

reachable = [False for _ in range(n)]
nodes = [0]
reachable[0] = True
while nodes:
    node = nodes.pop()
    for v in graph[node]:
        if not reachable[v]:
            reachable[v] = True
            nodes.append(v)

# print(graph)
topo = []

degs = original_degs[:]
bag = list(filter(lambda i: reachable[i] and (degs[i] == 0), range(n)))
while bag:
    v = bag.pop()
    topo.append(v)
    for neigh in froms[v]:
        if not reachable[neigh]:
            continue
        degs[neigh] -= 1
        if not degs[neigh]:
            bag.append(neigh)

def calc():
    vals = [0 for _ in range(n)]

    for v in topo:
        # print(f'calc for {v}')
        if not len(graph[v]):
            # print('no children')
            vals[v] = 1
        else:
            # print(f'{len(graph[v])} children')
            vals[v] = len(graph[v]) * lcm(*[vals[w] for w in graph[v]])
            # print(f'val is {vals[v]}')
    return vals

def push(vals, moves):
    to_move = [0 for _ in range(n)]
    to_move[0] = moves
    for v in range(n):
        vals[v] = to_move[v]
        # print(f'{v} moving {vals[v]} times')
        if not graph[v]:
            continue
        sub_moves = vals[v] // len(graph[v])
        for neigh in graph[v]:
            # print(f'{neigh} gets additional {sub_moves} from {v}')
            to_move[neigh] += sub_moves

def ok(times):
    # print(f'times: {times}')
    # print(f'vals: {vals}')
    status = [
        not reachable[i] 
        or 
        (
            times[i] 
            and 
            (
                not graph[i] 
                or 
                not (times[i] % len(graph[i]))
            ) 
        ) for i in range(n)
    ]
    # print(f'status: {status}')
    return all(
        status
    ) 
    # print(ret)
    # return ret

vals = calc()
# print(f'vals: {vals}')

# top_prime = 105
# notprimes = set(j for i in range(2, top_prime) for j in range(2 * i, top_prime, i))
# primes = [x for x in range(2, top_prime) if x not in notprimes]
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]
# print(primes)
ans = vals[0]
# print(ans)
# times = [0 for _ in range(n)]
# push(times, ans)
# if not ok(times):
#     raise RuntimeError()

for prime in primes:
    if (prime > ans) or (ans % prime):
        continue

    while True:
        nans = ans // prime
        # print(f'checking {nans}')
        times = [0 for _ in range(n)]
        push(times, nans)
        if not ok(times):
            break

        # print(f'{nans} becomes ans')
        ans = nans

print(ans)