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())