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

platforms = 0;
outs = [];

for line in sys.stdin:
    row = [int(i)-1 for i in line.split(" ")];
    outs.append(row);

platforms = outs.pop(0)[0];
for out in outs:
    out.pop(0);

def normalize(rat):
    n, d = rat;
    common = math.gcd(n,d);
    return (n//common,d//common);

def lcm(a,b):
  return (a * b) // math.gcd(a,b)

def plus(rat1,rat2):
    n1,d1 = rat1;
    n2,d2 = rat2;
    d = lcm(d1,d2);
    return (n1*(d//d1)+n2*(d//d2),d);

def divide(rat,div):
    n,d = rat;
    return normalize((n,d*div));

distributions = [(1,1)] + [(0,1)]*platforms;
flows = [];

for idx, out in enumerate(outs):
    if out:
        fn,fd = divide(distributions[idx],len(out));
        if fn > 0:
            flows.append(fd);
            for nxt in out:
                distributions[nxt] = plus(distributions[nxt], (fn,fd));
result = 1;
for flow in flows:
    result = lcm(result, flow);
print(result);