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
in_size = [0]*101
out_size = [0]*101
next_stat = [[] for i in range(101)]
prev_stat = [[] for i in range(101)]
reset_cycle = [0]*101
outs_in_reset = [0]*101


def GCD(a, b):
    # print(f"GCD {a} {b}")
    while b != 0:
        aux = b
        b = a % b
        a = aux
    return a


def LCM(a, b):
    gcd = GCD(a, b)
    adiv = int(a // gcd)
    return adiv * b


if __name__ == '__main__':
    n = int(input())
    for i in range(1, n+1):
        rxs = input().split()
        r = int(rxs[0])
        for j in range(r):
            x = int(rxs[j+1])
            if in_size[i] != 0 or i == 1:
                next_stat[i].append(x)
                prev_stat[x].append(i)
                in_size[x] += 1
                out_size[i] += 1

    #DEBUG
    # for i in range(1, n+1):
    #     print(f"PROPERTIES OF {i}:")
    #     print(f"IN_SIZE: {in_size[i]} | OUT_SIZE: {out_size[i]}")
    #     print(f"NEXTS: {next_stat[i]}")
    #     print(f"PREVS: {prev_stat[i]}")
    #     print("")

    reset_cycle[1] = out_size[1]
    outs_in_reset[1] = 1
    final_reset = 1
    for i in range(2, n+1):
        if in_size[i] == 0:
            continue

        parent_lcm = 1
        for j in range(in_size[i]):
            parent_lcm = LCM(parent_lcm, reset_cycle[prev_stat[i][j]])
            # print(f"PREDECESSOR: {prev_stat[i][j]}, THEIR RCYCLE: {reset_cycle[prev_stat[i][j]]}")
            # print(f"NODE {i}: PL after LCMed. by {reset_cycle[prev_stat[i][j]]} = {parent_lcm}")

        if out_size[i] == 0:
            reset_cycle[i] = parent_lcm
            final_reset = LCM(final_reset, parent_lcm)
            continue

        moves = 0
        for j in range(in_size[i]):
            par_cycles = parent_lcm // reset_cycle[prev_stat[i][j]]
            moves += par_cycles * outs_in_reset[prev_stat[i][j]]
        shortmoves = (moves - 1) % out_size[i] + 1
        needcycles = LCM(out_size[i], shortmoves) // shortmoves
        outs_in_reset[i] = moves * needcycles // out_size[i]
        reset_cycle[i] = needcycles * parent_lcm

        # print(f"NODE {i}: PL={parent_lcm}, M={moves}, nc={needcycles}, C={reset_cycle[i]}")

    print(int(final_reset))