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
import sys
import math


def simplify(f):
    a, b = f
    return a // math.gcd(a, b), b // math.gcd(a, b)


def add(f1, f2):
    a, b = f1
    c, d = f2
    return simplify((a * d + b * c, b * d))


def wal():
    graph = []
    n = int(sys.stdin.readline())
    for line in sys.stdin:
        ints = [int(x) for x in line.split()][1:]
        graph.append(ints)
    print("graph", graph, file=sys.stderr)
    edges = []
    nodes = [(1, 1)] + (n - 1) * [(0, 1)]
    print("nodes", nodes, file=sys.stderr)
    for i, neighboards in enumerate(graph):
        if len(neighboards) == 0:
            continue
        a, b = nodes[i]
        if a == 0:
            continue
        b *= len(neighboards)
        a, b = simplify((a, b))
        edges.append(b)
        for n in neighboards:
            nodes[n - 1] = simplify(add(nodes[n - 1], (a, b)))
        print(i, "nodes", nodes, file=sys.stderr)
    ret = 1
    print("edges", edges, file=sys.stderr)
    for e in edges:
        ret = math.lcm(ret, e)
    print(ret)


if __name__ == '__main__':
    wal()