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
# import numpy as np
from collections import deque

n = int(input())
v = []

for i in range(n):
    line = [int(x) for x in input().split()]
    v.append([j-1 for j in line[1:]])

indeg = [0] * n
indeg[0] = 1
for i in range(n):
    if (indeg[i] == 0):
        continue
    for j in v[i]:
        indeg[j] += 1
indeg[0] = 0

frac = [(0, 1)] * n
frac[0] = (1, 1)

def gcd(a, b):
    while (b != 0):
        c = a % b
        a = b
        b = c
    return a

def normalize(p, q):
    d = gcd(p, q)
    return (p//d, q//d)

# p1/q1 += p2/(q2*deg) => p1/q1 := normalize(p1*q2*deg + p2*q1, q1*q2*deg) 
def update_frac(u, x):
    deg = len(v[x])
    frac[u] = normalize(frac[u][0] * deg * frac[x][1] + frac[x][0] * frac[u][1], frac[u][1] * frac[x][1] * deg)

q = deque([0])

while len(q) > 0:
    x = q.popleft()
    for u in v[x]:
        update_frac(u, x)
        indeg[u] -= 1
        if indeg[u] == 0:
            q.append(u)

def finalize_frac():
    for i in range(n):
        deg = len(v[i]) if len(v[i]) != 0 else 1
        frac[i] = normalize(frac[i][0], frac[i][1] * deg)

def nww(x, y):
    return x*y//gcd(x, y)

def get_nww():
    res = 1
    for i in range(n):
        res = nww(res, frac[i][1])
    return res

finalize_frac()
print(get_nww())