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
import math
n = int(input())

g = [[] for i in range(n)]
deg = [0 for i in range(n)]
p = [0 for i in range(n)]
q = [1 for i in range(n)]
one = [0 for i in range(n)]
one[0] = 1
p[0] = 1;

for i in range(n):
	l = input().split(' ')
	k = int(l[0])
	for j in range(k):
		x = int(l[j + 1])
		g[i].append(x - 1)
		deg[x - 1] += 1

s = []

for i in range(n):
	if deg[i] == 0:
		s.append(i)

ans = 1;

while (len(s) > 0):
	x = s.pop()
	if one[x]:
		me = 0;
		if (len(g[x]) == 0):
			me = q[x]
		else:
			gd = math.gcd(p[x], len(g[x]))
			me = q[x] * len(g[x]) // gd
		gd = math.gcd(ans, me)
		ans = ans * me // gd
	for y in g[x]:
		a = p[x]
		b = q[x] * len(g[x])
		c = p[y]
		d = q[y]
		e = a * d + c * b
		f = b * d
		gd = math.gcd(e, f)
		p[y] = e // gd
		q[y] = f // gd
		#print(y, p[y], q[y]);
		if one[x] == 1:
			one[y] = 1
		deg[y] -= 1
		if (deg[y] == 0):
			s.append(y)
print(ans)