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
#/usr/bin/env python3

import math


def load_data():
    n = int(input())
    forward_edges = [[1]]
    backward_edges = [[] for _ in range(n + 2)]
    backward_edges[1] = [0]
    for i in range(1, n + 1):
        edges = list(map(int, input().split()))[1:]
        for nb in edges:
            backward_edges[nb].append(i)
        forward_edges.append(edges)
    return forward_edges, backward_edges


def main():
    forward_edges, backward_edges = load_data()

    result = 1
    visit_counts = [0] * len(forward_edges)
    visit_counts[0] = 1

    for curr_idx in range(1, len(forward_edges)):
        curr_visit_count = 0
        for nb_idx in backward_edges[curr_idx]:
            curr_visit_count += visit_counts[nb_idx] // len(forward_edges[nb_idx])

        if curr_visit_count == 0:
            continue

        visit_counts[curr_idx] = curr_visit_count

        outdeg = len(forward_edges[curr_idx])
        if outdeg == 0:
            continue

        if curr_visit_count % outdeg != 0:
            mult = outdeg // math.gcd(curr_visit_count, outdeg)
            result *= mult
            for visited_idx in range(curr_idx + 1):
                visit_counts[visited_idx] *= mult

    print(result)


main()