n = int(input()) g = [[int(x)-1 for x in input().split()][1:] for _ in range(n)] def euclid(a, b): if b == 0: return (a,1,0) (d, y, x) = euclid(b,a%b) return (d, x, y-a//b*x) def solve(a,m): return m//euclid(a%m,m)[0] def simulate(x, values): waiting = list(tuple(values)) waiting[0] += x for u in range(n): for (j, v) in enumerate(g[u]): waiting[v] += waiting[u]//len(g[u]) + (1 if waiting[u]%len(g[u]) > j else 0) waiting[u] %= max(1,len(g[u])) return waiting values = simulate(1, [0]*n) res = 1 for i in range(n): if values[i] != 0: needed = solve(values[i], len(g[i])) res *= needed values = simulate(res, [0]*n) print(res)
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 | n = int(input()) g = [[int(x)-1 for x in input().split()][1:] for _ in range(n)] def euclid(a, b): if b == 0: return (a,1,0) (d, y, x) = euclid(b,a%b) return (d, x, y-a//b*x) def solve(a,m): return m//euclid(a%m,m)[0] def simulate(x, values): waiting = list(tuple(values)) waiting[0] += x for u in range(n): for (j, v) in enumerate(g[u]): waiting[v] += waiting[u]//len(g[u]) + (1 if waiting[u]%len(g[u]) > j else 0) waiting[u] %= max(1,len(g[u])) return waiting values = simulate(1, [0]*n) res = 1 for i in range(n): if values[i] != 0: needed = solve(values[i], len(g[i])) res *= needed values = simulate(res, [0]*n) print(res) |