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

def safe_deg(deg):
    return 1 if deg == 0 else deg

class dag:
    def __init__(self, n, v_descs):
        self.n = n
        self.degree = []
        self.neighbours = []
        self.charge = [0] * n
        for d in v_descs:
            spl = d.split()
            deg = int(spl[0])
            self.degree.append(deg)
            ns = []
            for i in range(1, deg + 1):
                ns.append(int(spl[i])-1)
            self.neighbours.append(ns)
    
    def throw_luggage(self, count):
        i = 0
        self.charge[0] = count // safe_deg(self.degree[0])
        for i in range(self.n):
            for j in self.neighbours[i]:
                self.charge[j] += self.charge[i] // safe_deg(self.degree[j])

def nwd(a,b):
    r = a%b
    while r != 0:
        a = b
        b = r
        r = a%b
    return b

n = int(sys.stdin.readline())
v_descs = []
for i in range(n):
    v_descs.append(sys.stdin.readline())

graph = dag(n, v_descs)

degprod = 1
for deg in graph.degree:
    degprod = degprod * safe_deg(deg)

graph.throw_luggage(degprod)

denominator = graph.charge[0]
for i in range(1,n):
    if graph.charge[i] > 0:
        denominator = nwd(denominator, graph.charge[i])

print(graph.charge[0] // denominator * safe_deg(graph.degree[0]))