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

def GCD(a,b):
    while b != 0:
        if a < b:
            a,b = b,a
        a,b = b , a%b
    return a

def main():
    data = sys.stdin.readlines()
    N = int(data[0])
    E = [[] for i in range(N)]
    BE = [[] for i in range(N)]
    for i in range(N):
        L = list(map(int,data[i+1].split()))
        for j in L[1:]:
            x = j-1
            E[i].append(x);
            BE[x].append(i);

    if len(E[0]) == 0:
        print(1)
        return 0

    cnt = N*[0];
    cnt[0] = len(E[0])

    for i in range(1,N):
        cnt[i] = 0;
        for x in BE[i]:
            cnt[i] += cnt[x] // len(E[x])
        #print(cnt[i])
        if len(E[i]) == 0:
            continue
        if cnt[i] % len(E[i]) != 0:
            gcd = GCD(cnt[i],len(E[i]))
            #print(gcd)
            mul = len(E[i])//gcd
            #print(mul)
            for k in range(i+1):
                cnt[k] *= mul
        #for k in range(N):
        #    print(cnt[k])
    print(cnt[0])
    return 0;
    

if __name__ == "__main__":
    main()