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 65 66 67 68 69 70 71 72 73 74 75 76 def gcd(a, b): while b != 0: r = a % b a = b b = r return a class Platform: def __init__(self, p_num): self.num = p_num self.incoming = [] self.outgoing = [] def add_edge_to(self, p_platform): self.outgoing.append(p_platform) p_platform.incoming.append(self) def show(self): incoming = [str(p.num) for p in self.incoming] outgoing = [str(p.num) for p in self.outgoing] print(f'{self.num} incoming: {",".join(incoming)} outgoing: {",".join(outgoing)}') class Solver: def __init__(self): self.n = 0 # number of platforms self.platforms = [None] # platform indexed from 1 def read_data(self): self.n = int(input().strip()) self.platforms = [None] * (self.n + 1) for i in range(self.n): self.platforms[i+1] = Platform(i+1) for i in range(self.n): num = i+1 inp = input().strip().split(' ') m = int(inp[0]) for j in range(m): target = int(inp[j+1]) self.platforms[i+1].add_edge_to(self.platforms[target]) def show_data(self): for i in range(self.n): self.platforms[i+1].show() def calculate(self): if len(self.platforms[1].outgoing) == 0: return 1 o = [0] * (self.n+1) o[1] = 1 for i in range(2, self.n+1): p = self.platforms[i] d = len(p.outgoing) # print(f"calculating for i={i} d={d}") if d == 0: o[i] = 1 continue received = 0 for in_platform in p.incoming: received += o[in_platform.num] if received == 0: o[i] = 0 else: factor = d // gcd(d, received) for j in range(1, i): o[j] *= factor o[i] = (received * factor) // d # for j in range(1, i+1): # print(f" {o[j]}") return o[1] * len(self.platforms[1].outgoing) s = Solver() s.read_data() print(s.calculate())