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
from fractions import *
from math import lcm

F = Fraction

n = int(input())

adj_in = [[] for i in range(n)]
adj_out = [[] for i in range(n)]

for v in range(n):
    linia = list(map(int, input().split()))[1:]
    for u in linia:
        adj_out[v].append(u - 1)
        adj_in[u - 1].append(v)

topo = []
odw = [False for i in range(n)]

def jazda(v):
    if not odw[v]:
        odw[v] = True
        for u in adj_out[v]:
            jazda(u)
        topo.append(v)

jazda(0)

topo = topo[::-1]

odp = 1
wart = [None for i in range(n)]
for v in topo:
    if adj_out[v]:
        if v == 0:
            wart[v] = F(1, len(adj_out[v]))
        else:
            wart[v] = F(0)
            for u in adj_in[v]:
                if odw[u]:
                    wart[v] += wart[u]
            wart[v] = wart[v] / F(len(adj_out[v]))
            odp = lcm(odp, wart[v].denominator)
    else:
        wart[v] = F(0)
    #print(v + 1, wart[v])
print(odp)