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
#!/bin/python3
from math import lcm

if __name__ == "__main__":
    n = int(input())
    # vertex - (edges_out, edges_in)
    graph = [([], []) for i in range(n)]
    for i in range(n):
        edges_out = [int(l) - 1 for l in input().split()[1:]]
        graph[i][0].extend(edges_out)
        for e in edges_out:
            graph[e][1].append(i)
    
    period = [0] * n
    cnt_out = [0] * n

    cnt_out[0] = 1
    period[0] = max(1, len(graph[0][0]))

    for i in range(1, n):
        prev_period = period[i - 1]
        cnt_in = 0
        for edge_in in graph[i][1]:
            n_periods = prev_period // period[edge_in]
            cnt_in += n_periods * cnt_out[edge_in]

        n_edges_out = len(graph[i][0])
        if cnt_in == 0 or n_edges_out == 0:
            period[i] = period[i - 1]
            cnt_out[i] = 0
            continue

        new_period_out = lcm(cnt_in, n_edges_out)
        period[i] = new_period_out // cnt_in * prev_period
        cnt_out[i] = new_period_out // n_edges_out

    print(period[-1])