Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N = int(input())
en = [[] for _ in range(N)]
on = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2:
        on[u - 1].append(v - 1)
        on[v - 1].append(u - 1)
    else:
        en[u - 1].append(v - 1)
        en[v - 1].append(u - 1)

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N = int(input())
en = [[] for _ in range(N)]
on = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2:
        on[u - 1].append(v - 1)
        on[v - 1].append(u - 1)
    else:
        en[u - 1].append(v - 1)
        en[v - 1].append(u - 1)

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")
### BUGGY CODE ###

from fractions import gcd

n=int(input())
a=list(map(int,input().split()))

lcm=1
for i in a:
 lcm=(lcm*i)//gcd(lcm,i)

ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)

### FIXED CODE ###

from fractions import gcd

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

'''
lcm=1
for i in a:
 lcm=(lcm*i)//gcd(lcm,i)

ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)
'''

from functools import reduce

lcm=reduce(lambda x,y :(x*y)//gcd(x,y),a)

'''
ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
'''
ans=sum(lcm//i for i in a)
ans%=mod
print(ans)
### BUGGY CODE ###

X = int(input())

for i in range(X, 0, -1):
    tmp = i
    if X % tmp:
        continue
    while tmp <= X:
        tmp *= tmp
    if tmp == X:
        print(i)


### FIXED CODE ###

X = int(input())

ans = 1
for i in range(1, X):
    for j in range(2, X):
        tmp = i ** j
        if tmp > X:
            break
        ans = max(tmp, ans)
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
B = [0]*(n-1)
for i in range(n-1):
    B[i]=abs(sum(A[0:i+1])-sum(A[i+1:n]))
print(min(B))

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
Asum = sum(A)
Al = 0
ans = Asum
for a in A:
    Al += a
    Ar = Asum-Al
    ans = min(ans,abs(Ar-Al))
print(ans)
### BUGGY CODE ###

N = int(input())
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト(繋がっている先, コスト)
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    prev = [None] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                prev[v] = u
                heappush(pq, (dist[v], v))
    return dist
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))
shortest_path = [dijkstra(graph, i) for i in range(N)]
Q, K = map(int, input().split())
for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x-1][K-1]+shortest_path[K-1][y-1])


### FIXED CODE ###

N = int(input())
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト(繋がっている先, コスト)
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    prev = [None] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                prev[v] = u
                heappush(pq, (dist[v], v))
    return dist
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))
Q, K = map(int, input().split())
shortest_path_K = dijkstra(graph, K-1)
for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path_K[x-1]+shortest_path_K[y-1])
### BUGGY CODE ###

n=int(input())
a=0
for i in range(1,n+1):
  for j in range(1,n+1):
    if str(i)[0]==str(j)[-1] and str(j)[0]==str(i)[-1]:
      a+=1
print(a)

### FIXED CODE ###

n=int(input())
t=[[0]*10 for _ in range(10)]
for i in range(1,n+1):
  t[int(str(i)[0])][i%10]+=1
a=0
for i in range(10):
  for j in range(10):
    a+=t[i][j]*t[j][i]
print(a)
### BUGGY CODE ###

import sys
import math
import copy

def is_prime(N):
    if N == 1:
        return False
    i = 2
    while i * i <= N:
        if N % i == 0:
            return False
        i += 1
    return True


def main():
    N = int(input())
    if N == 1:
        print(0)
        sys.exit()
    if is_prime(N):
        print(1)
        sys.exit()
    else:
        count = 0
        ori_N = copy.copy(N)
        for i in range(2, ori_N):
            if N < i:
                break
            if N % i == 0:
                if is_prime(i):
                    count += 1
                    N //= i
                else:
                    j = 2
                    while i % j != 0:
                        j += 1
                    now = i
                    while now > j:
                        now /= j
                        if now == j:
                            count += 1
                            N //= i
        print(count)

if __name__ == '__main__':
     main()



### FIXED CODE ###

import sys
import math


def is_prime(N):
    if N == 1:
        return False
    i = 2
    while i * i <= N:
        if N % i == 0:
            return False
        i += 1
    return True

def prime(N):
    prime = []
    is_prime = []  # 全て素数であると初期化
    for i in range(N):
        if i * i > N:
            break
        is_prime.append(True)
    is_prime[0] = is_prime[1] = False # 0,1は素数ではない
    n = len(is_prime)
    for i in range(2, n):
        if is_prime[i]:
            # iは素数である
            prime.append(i)
            for j in range(2 * i, n, i):
                # iの倍数は素数でない
                is_prime[j] = False
    # N以下の素数を表示
    return prime, n

def main():
    N = int(input())
    if N == 1:
        print(0)
    else:
        if is_prime(N):
            print(1)
        else:
            prime_list, n = prime(N)
            used = []
            prime_exponentiation = []
            count = 0
            for i in range(len(prime_list)):
                now = prime_list[i]
                j = 1
                while now ** j <= N:
                    prime_exponentiation.append(now ** j)
                    j += 1
            prime_exponentiation.sort()
            for i in range(len(prime_exponentiation)):
                now = prime_exponentiation[i]
                if N < now:
                    j = 0
                    while not is_prime(N):
                        if N == 1:
                            break
                        while N % prime_list[j] == 0:
                            N //= prime_list[j]
                        j += 1 
                    break
                if N % now == 0:
                    count += 1
                    used.append(now)
                    N //= now
            if N not in used and N != 1:
                count += 1
            print(count)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

"""
解説を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = massHi[Wi]
            if massHi[Wi] == 1:
                queue1.append([Hi, Wi])
    # import datetime
    # d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if w != 0 and mass[h][w - 1] == 0:
                mass[h][w - 1] = 1
                queue2.append([h, w - 1])
            # right
            if w < W - 1 and mass[h][w + 1] == 0:
                mass[h][w + 1] = 1
                queue2.append([h, w + 1])
            # top
            if h < H - 1 and mass[h + 1][w] == 0:
                mass[h + 1][w] = 1
                queue2.append([h + 1, w])
            # button
            if h != 0 and mass[h - 1][w] == 0:
                mass[h - 1][w] = 1
                queue2.append([h - 1, w])

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
解説と提出 #5747380を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    # mass = [[False] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  # 外枠
    for Hi in range(1, H + 1):
        mass.append([False] + [s == '.' for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append((Hi, Wi))
    mass.append([False] * (W + 2))  # 外枠
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append((h, w - 1))
            # right
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append((h, w + 1))
            # top
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append((h + 1, w))
            # button
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append((h - 1, w))

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

s=[i for i in input()]
cnt=0
while True:
    if len(s)==0 or s.count("0")==len(s) or s.count("1")==len(s):
        break
    else:
        for i in range(len(s)):
            try:
                if int(s[i])+int(s[i+1])==1:
                    cnt+=2
                    s=s[0:i]+s[i+2:]
            except:
                pass
print(cnt)

### FIXED CODE ###

s=[i for i in input()]
one=s.count("1")
zero=s.count("0")
print(len(s)-abs(one-zero))
### BUGGY CODE ###

from fractions import Fraction
from math import ceil
import heapq
n,k, *aa = map(int, open(0).read().split())

hq = [(-a,-1,-a) for a in aa]
heapq.heapify(hq)

for _ in range(k):
    v,cnt,orig = heapq.heappop(hq)
    cnt *= -1
    cnt += 1
    v = orig / cnt
    cnt *= -1
    heapq.heappush(hq, (v,cnt,orig))

print(max([ceil(-a) for a,b,c in hq]))

### FIXED CODE ###

from math import ceil

n,k, *aa = map(int, open(0).read().split())

left = 0
right = 10**9

while right - left > 1:
    mid = (left + right) // 2
    summ = sum(0--a//mid-1 for a in aa)
    if summ <= k:
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy

def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        tmp = a[i]
        a[i] = -1
        tmp_a_c = Counter(a)
        tmp_a_cc = [tmp_a_c[i] for i in tmp_a_c if tmp_a_c[i] > 1]
        r = 0
        for cc in tmp_a_cc:
            r += factorial(cc) // (2 * factorial(cc-2))
        print(r)
        a[i] = tmp


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_c = Counter(a)
    a_c_sum = 0
    for c in a_c:
        if a_c[c] >= 2:
            a_c_sum += cmb(a_c[c], 2)

    for ea in a:
        if a_c[ea] <= 1:
            sa = 0
        elif a_c[ea] == 2:
            sa = 1
        else:
            sa = cmb(a_c[ea], 2) - cmb(a_c[ea] - 1, 2)
        print(a_c_sum - sa)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np

h, n = map(int, input().split())

a = []
b = []
m = []
for i in range(n):
    at, bt = map(int, input().split()) # a_tmp, b_tmp
    a.append(at)
    b.append(bt)

dp = np.zeros((n+1,h+1))

for i in range(n):
    for j in range(h):
        # print("Test")
        if j - a[i] < 0:
            o = b[i]
        else:
            o = dp[i+1][j+1-a[i]] + b[i]
        if i != 0:
            dp[i+1][j+1] = min(dp[i][j+1], o)
        else:
            dp[i+1][j+1] = o

print(int(dp[n][h]))

### FIXED CODE ###

#import numpy as np

h, n = map(int, input().split())

a = []
b = []
m = []
for i in range(n):
    at, bt = map(int, input().split()) # a_tmp, b_tmp
    a.append(at)
    b.append(bt)

#dp = np.zeros((n+1,h+1))
dp = [[0]*(h+1) for _ in range(n+1)]
for i in range(n):
    for j in range(h):
        # print("Test")
        if j - a[i] < 0:
            o = b[i]
        else:
            o = dp[i+1][j+1-a[i]] + b[i]
        if i != 0:
            dp[i+1][j+1] = min(dp[i][j+1], o)
        else:
            dp[i+1][j+1] = o

print(int(dp[n][h]))
### BUGGY CODE ###


N = int(input())
S = []

ans = 0

for i in range(N):
    S.append(sorted(input()))

for i in range(N):
    s_i = S[i]

    for j in range(i+1, N):
        s_j = S[j]

        if s_i == s_j:
            ans += 1


print(ans)

### FIXED CODE ###


def combain(X, Y):
    return int(( X * (X - 1)) / Y)

N = int(input())
S = []

ans = 0

for i in range(N):
    S.append(sorted(input()))

S.sort()

ans = 0

X = 1
for i in range(N-1):
    if S[i] == S[i+1]:
        X += 1
    elif X > 1:
        C = combain(X, 2)
        X = 1
        ans += C

if X > 1:
    C = combain(X, 2)
    X = 1
    ans += C
    
print(ans)
### BUGGY CODE ###

# import numpy as np
# import matplotlib.pyplot as plt
# from matplotlib.image import imread
def init():
    global N, Sp, Sm
    N = int(input())
    Sp = []
    Sm = []
    for i in range(N):
      l = input()
      u = 0
      h = 0
      for j in range(len(l)):
        if l[j] == '(':
          h += 1
        else:
          h -= 1
        if h < u:
          u = h
      if h >= 0:
        Sp.append([u, h])
      else:
        Sm.append([u-h, -h])
    Sp.sort(reverse=True)
    Sm.sort(reverse=True)

def main():
  init()
  p = check(Sp)
  m = check(Sm)
  if p != -1 and m != -1 and p ==m:
    print('Yes')
  else:
    print('No')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline().strip()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []

for i in range(1, n+1):
    num = a.index(i)
    b.append(num+1)

print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n

for i in range(0, n):
    b[a[i]-1] = i + 1


print(' '.join(map(str, b)))
### BUGGY CODE ###

N,X,Y = map(int,input().split())
A = []
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A.append(min([b-a,abs(X-a)+abs(Y-b)+1]))
for i in range(1,N):
    print(A.count(i))

### FIXED CODE ###

N,X,Y = map(int,input().split())
A = [0 for i in range(N)]
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A[min([b-a,abs(X-a)+abs(Y-b)+1])] += 1
for i in range(1,N):
    print(A[i])
### BUGGY CODE ###

answer = 1
lens = int(input())
arrs = [int(x) for x in input().split()]
for x in arrs:
    answer *= x
if answer > int(10 ** 18):
    answer = -1
print(answer)


### FIXED CODE ###

answer = 1
lens = int(input())
arrs = [int(x) for x in input().split()]
if 0 in arrs:
    answer = 0
else:
    for x in arrs:
        answer *= x
        if answer > int(10 ** 18):
            answer = -1
            break
print(answer)
### BUGGY CODE ###

N = int(input())

station = [list(map(int, input().split())) for i in range(N - 1)]



def next_start_time(arrive, C, S, F):
    for i in range(1000):
        if arrive > S:
            i = (arrive - S) // F
            if arrive <= S + i * F:
                break
            else:
                i = i + 1
        elif arrive <= S + i * F:
            break
    return S + (i * F) + C


for i in range(N - 1):
    ans = 0
    for j in range(i, N - 1):
        ans = next_start_time(ans, station[j][0], station[j][1], station[j][2])
    print(ans)

print(0)

### FIXED CODE ###

N = int(input())

station = [list(map(int, input().split())) for i in range(N - 1)]



def next_start_time(arrive, C, S, F):
    for i in range(1000):
        if arrive > S:
            i = (arrive - S) // F
            if arrive <= S + i * F:
                break
            else:
                i = i + 1
                break
        elif arrive <= S + i * F:
            break
    return S + (i * F) + C


for i in range(N - 1):
    ans = 0
    for j in range(i, N - 1):
        ans = next_start_time(ans, station[j][0], station[j][1], station[j][2])
    print(ans)

print(0)
### BUGGY CODE ###

S = input()
Q = int(input())
rotate = 1
for i in range(Q):
    n = [str(i) for i in input().split()]
    if n[0] == "1":
        rotate *= -1
    else:
        if n[1] == "1":
            if rotate == 1:
                S = n[2] + S
            else:
                S = S + n[2]
        else:
            if rotate == 1:
                S = S + n[2]
            else:
                S = n[2] + S
if rotate == 1:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
left = deque()
right = deque()
rotate = 1
for i in range(Q):
    n = [str(i) for i in input().split()]
    if n[0] == "1":
        rotate *= -1
    else:
        if n[1] == "1":
            if rotate == 1:
                left.appendleft(n[2])
            else:
                right.append(n[2])
        else:
            if rotate == 1:
                right.append(n[2])
            else:
                left.appendleft(n[2])
left = list(left)
right = list(right)
ans = "".join(left)
ans += S
ans += "".join(right)
if rotate == 1:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
            else:
                if d > i:
                    ql.append([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


if __name__ == '__main__':
    slove()