Harryxun/stf_run huggingface dataset:
def dfs(a,adjl,visited,dp):
  for i in adjl[a]:
    if visited[i]==0:
      visited[i]=1
      dfs(i,adjl,visited,dp)
 
    dp[a]=max(dp[a],1+dp[i])
n,m=map(int,input().split())
li=[]
for i in range(m):
  li.append([int(k) for k in input().split()])
adjl=[[] for j in range(n+1)]
for k in range(len(li)):
  adjl[li[k][0]].append(li[k][1])
visited=[0]*(n+1)
dp=[0]*(n+1)
for a in range(1,n+1):
  if visited[a]==0:
    visited[a]=1
    dfs(a,adjl,visited,dp)
print(max(dp))

  

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
def dfs(a,adjl,visited,dp):
  for i in adjl[a]:
    if visited[i]==0:
      visited[i]=1
      dfs(i,adjl,visited,dp)
 
    dp[a]=max(dp[a],1+dp[i])
n,m=map(int,input().split())
li=[]
for i in range(m):
  li.append([int(k) for k in input().split()])
adjl=[[] for j in range(n+1)]
for k in range(len(li)):
  adjl[li[k][0]].append(li[k][1])
visited=[0]*(n+1)
dp=[0]*(n+1)
for a in range(1,n+1):
  if visited[a]==0:
    visited[a]=1
    dfs(a,adjl,visited,dp)
print(max(dp))
# coding:utf-8

N, X = map(int, input().split())

def eatBan(c, w):
        return c, w+1
def eatPan(c, w):
    return c+1, w+1
def checkWalk(w, X):
    if w == X:
        return True
    else:
        return False

def createNBurger(w, c, n, X):
    if n == 0:
        c, w = eatPan(c, w)
        return c, w
    else:
        # バン食べる
        c, w = eatBan(c, w)
        if checkWalk(w, X):
            c, w, True
        # N-1 バーガー
        c, w = createNBurger(w, c, n-1, X)
        if checkWalk(w, X):
            c, w, True
        # パティ食べる
        c, w = eatPan(c, w)
        if checkWalk(w, X):
            c, w, True
        # N-1 バーガー
        c, w = createNBurger(w, c, n-1, X)
        if checkWalk(w, X):
            return c, w, True
        # バン食べる
        c, w = eatBan(c, w)
        if checkWalk(w, X):
            c, w, True
        return c, w, False

# Nバーガー作成
c = 0
w = 0
c, w , t= createNBurger(w, c, N, X)

# eat_p = 0
# for i, c in enumerate(burger):
#     if c == "P":
#         eat_p += 1
#     if i == X-1:
#         break
print(c)

### FIXED CODE ###

# coding:utf-8

d = int(input())

c_eve = 25 - d

out = "Christmas"

for i in range(c_eve):
    out += " Eve"

print(out)
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)

# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)

# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - (A+1) - (x + y - z)
print(not_d)


### FIXED CODE ###

""" import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)

# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)

# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - (A+1) - (x + y - z)
print(int(not_d))
 """

a, b, c, d = map(int, input().split())

total = b - a + 1


def lem(A, B):
	AB = A * B
	while B != 0:
		A, B = B, A % B
	return AB // A


bsep = (b // c) + (b // d) - (b // lem(c, d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c, d)

ans = total - bsep + asep
print(ans)
n,m,k = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A,B = [0],[0]
 
for i in range(n):
  A.append(a[i] + A[i])
for i in range(m):
  B.append(b[i] + B[i])
 
num,x = 0,m-1
A.pop(0)
B.pop(0)
 
for i in range(len(a)):
  if A[i] > k:
    break
  while A[i] + B[x] > k:
    x -= 1
  num = max(num, i + x + 2)
  
print(num)
 

### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A,B = [0],[0]

for i in range(n):
  A.append(a[i] + A[i])
for i in range(m):
  B.append(b[i] + B[i])

num,x = 0,m

for i in range(n+1):
  if A[i] > k:
    break
  while A[i] + B[x] > k:
    x -= 1
  num = max(num, i + x)
  
print(num)
S = input()
X, Y = map(int, input().split())

A = [0]
for s in S:
    if s == 'T':
        A.append(0)
    else:
        A[-1] += 1

B = [n for n in A[1:: 2]]
X -= A[0]
A = [n for n in A[2:: 2]]

def canGo(nums, g):
    if not nums:
        return g == 0

    bias = sum(nums) + 10
    g += bias
    dp = (1 << bias)

    for n in nums:
        dp = (dp << n) | (dp >> n)
    return (dp & (1 << g)) > 0

if canGo(A, X) and canGo(B, Y):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S = input()
X, Y = map(int, input().split())

A = [0]
for s in S:
    if s == 'T':
        A.append(0)
    else:
        A[-1] += 1

B = [n for n in A[1:: 2]]
X -= A[0]
A = [n for n in A[2:: 2]]

def canGo(nums, g):
    if not nums:
        return g == 0

    bias = sum(nums) + 10
    g += bias
    if g < 0:
        return False

    dp = (1 << bias)

    for n in nums:
        dp = (dp << n) | (dp >> n)
    return (dp & (1 << g)) > 0

if canGo(A, X) and canGo(B, Y):
    print('Yes')
else:
    print('No')
r = int(input())
pi = 3.1415926535
area = 2*pi*r
circumference = pi*r**2
print("{0:.6f} {1:.6f}".format(area, circumference))

### FIXED CODE ###

import math
r = float(input())
circumference = math.pi*r**2
area = 2*math.pi*r
print("{0:.6f} {1:.6f}".format(circumference, area))
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edges=[[] for i in range(n)]
inp=sys.stdin.buffer.readlines()
for i in inp[:n-1]:
    a,s=map(int,i.split());a-=1;s-=1
    edges[a].append(s)
    edges[s].append(a)
cnt=[-1]*n
add=[0]*n
for _ in inp[n-1:]:
    a,s=map(int,_.split())
    add[a-1]+=s


def f(x):
    if cnt[x]!=-1:return 0
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=str(ret)
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(' '.join(cnt))

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)
import math
import collections
A,B = map(int,input().split())
GCD = math.gcd(A,B)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

Bunkai = factorization(GCD) 
print(len(Bunkai) + 1)





### FIXED CODE ###

import fractions
A,B = map(int,input().split())
GCD = fractions.gcd(A,B)
if GCD == 1:
    print(1)
    exit()
    
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

Bunkai = factorization(GCD) 
print(len(Bunkai) + 1)
n , k = list(map(int, input().split()))
kaijou = []
kaijou.append(1)
kaijou.append(1)
i = 2
mod = 10 ** 9 + 7
while(i <= n):
    kaijou.append(i * kaijou[i - 1])
    i += 1
for i in range(1, k + 1):
    if i <= n - k + 1:
        b = kaijou[k - 1] / (kaijou[i - 1] * kaijou[k - i])
        a = kaijou[n - k + 1] / ( kaijou[i] * kaijou[n - k + 1 - i])
        print(int((a * b) % mod))
    else:
        print(0)

### FIXED CODE ###

import numpy as np
import math

n , k = list(map(int, input().split()))
def combi(a,b):
    return  math.factorial(a) // (math.factorial(b) * math.factorial(a-b))
i = 2
mod = 10 ** 9 + 7
for i in range(1, k + 1):
    if n - k + 1 >= i and k - 1 >= i - 1:
        print(int(combi(n - k + 1,i) * combi(k - 1, i - 1) % mod))
    else:
        print(0)
s = str(input()); n = len(s)
gx,gy = map(int,input().split())
Yoko = []; Tate = []
Flag = 0; cnt = 0
Max_x = 0; Max_y = 0
for i in range(n):
  if s[i] == "F":
    cnt += 1
    if i == n-1: #最後なら登録
      if Flag == 0:
        Max_x += cnt
        Yoko.append(cnt)
      else:
        Max_y += cnt
        Tate.append(cnt)      
  else: #T
    if Flag == 0:
      Max_x += cnt
      Yoko.append(cnt)
    else:
      Max_y = cnt
      Tate.append(cnt)
    cnt = 0
    Flag = Flag^1
#print(Yoko,Tate)
MAX_dpx = Max_x*2+1
dp = [0 for _ in range(MAX_dpx)]
dp[Max_x] = 1

for i,x in enumerate(Yoko):
  p = [0 for _ in range(MAX_dpx)]
  p,dp = dp,p
  for j in range(MAX_dpx):
    if i == 0: #i=0の時は右向きだけ
      if 0<=j+x<MAX_dpx:
        dp[j+x] = max(dp[j+x], p[j])
    else:
      if 0<=j+x<MAX_dpx:
        dp[j+x] = max(dp[j+x], p[j])
      if 0<=j-x<MAX_dpx:
        dp[j-x] = max(dp[j-x], p[j])
  #print(dp)
#print(dp)
#print(gx+Max_x,MAX_dpx)
if gx+Max_x >= MAX_dpx or dp[gx+Max_x] == 0:
  print("No");exit()

MAX_dpy = Max_y*2+1
dp = [0 for _ in range(MAX_dpy)]
dp[Max_y] = 1

for i,y in enumerate(Tate):
  p = [0 for _ in range(MAX_dpy)]
  p,dp = dp,p
  for j in range(MAX_dpy):
    if 0<=j+y<MAX_dpy:
       dp[j+y] = max(dp[j+y], p[j])
    if 0<=j-y<MAX_dpy:
      dp[j-y] = max(dp[j-y], p[j])
  #print(dp)
#print(dp)
if gy+Max_y >= MAX_dpy or dp[gy+Max_y] == 0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

S = str(input())
N = len(S)
x,y = map(int,input().split())
X = []; Y =[]
Flag = True #Trueならx軸、Falseならy軸
seq = 0
for i in range(N):
  if S[i] == "T":
    if Flag:
      X.append(seq)
    if not Flag:
      Y.append(seq)
    Flag = not Flag
    seq = 0
  else:
    seq += 1
    if i == N-1:
      if Flag:
        X.append(seq)
      if not Flag:
        Y.append(seq)
#print(X,Y)
num = 8100 #真ん中
MAX = num*2+1
#X方向i回目でjにいる
dpx = [0 for _ in range(MAX)]
dpx[num] = 1
dpy = [0 for _ in range(MAX)]
dpy[num] = 1
for i in range(len(X)):
  px = [0 for _ in range(MAX)]
  px,dpx = dpx,px
  step = X[i]
  for j in range(MAX):
    if j -step >= 0:
      dpx[j] = max(dpx[j],px[j-step])
    if j + step < MAX and i != 0: #一番最初は左に戻れない
      dpx[j] = max(dpx[j],px[j+step])
for i in range(len(Y)):
  py = [0 for _ in range(MAX)]
  py,dpy = dpy,py
  step = Y[i]
  for j in range(MAX):
    if j -step >= 0:
      dpy[j] = max(dpy[j],py[j-step])
    if j + step < MAX:
      dpy[j] = max(dpy[j],py[j+step])
x += num;y+= num
#print(dpx)
#print(dpy)
if dpx[x] == 1 and dpy[y] == 1:
  print("Yes")
else:
  print("No")
a, b, c = map(int, input().split())
if a % 3 == 0 and b % 3 != 0 and (a + b) % 3 != 0:
  print("possible")
elif b % 3 == 0 and a % 3 != 0 and (a + b) % 3 != 0:
  print("possible")
elif (a + b) % 3 == 0 and a % 3 != 0 and a % 3 != 0:

### FIXED CODE ###

a, b = map(int, input().split())
if a%3 == 0 or b%3 == 0 or (a+b)%3 == 0:
  print("Possible")
else:
  print("Impossible")
N=int(input())
A=list(map(int,input().split()))
ans=0

while True:
  for i in range(N):
    if A[i]&1==0:
      A[i]=A>>1
    else:
      print(ans)
      return
  ans+=1

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
flag=0

while flag==0:
  for i in range(N):
    if A[i]&1==0:
      A[i]=A[i]>>1
    else:
      print(ans)
      flag=1
      break
  ans+=1
import sys

print(sys.argv[3])

### FIXED CODE ###

D, T, S = map(int, input().split())
print("Yes" if T * S >= D else "No")
n,p=map(int,input().split())
a = list(map(int,input().split()))
for a_ in a:
    if not a_%2==0:
        k=1
        break
if k:
    print(1<<(n-1))
else:
    print(0) if p==1 else print(1<<n)

### FIXED CODE ###

n,p=map(int,input().split())
a = list(map(int,input().split()))
k=0
for a_ in a:
    if not a_%2==0:
        k=1
        break
if k:
    print(1<<(n-1))
else:
    print(0) if p==1 else print(1<<n)
n=list(input())
if sum(n)%9==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=input()
ls=[]
for i in n:
    ls.append(int(i))
if sum(ls)%9==0:
  print("Yes")
else:
  print("No")
N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
for i in range(N-1):
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。
ans = [-1 for _ in range(N-1)]

#vという頂点からpという親にcolorという色で繋がっている。
def dfs(v, color, p):
  k = 1 #色の初期値
  for i in range(len(g[v])): #vから繋がっている頂点をtoとして探す
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: #親は一つでそれ以外は子。親の時だけ無視すればよい。
      continue
    if k == color: #親から繋がっている色と被ったらダメ。
      k += 1
    ans[ID] = k
    k += 1 #ここで足す1をしないとこのfor loopの中の辺で色が被る。
    dfs(TO,ans[ID],v)

dfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
for i in range(N-1):
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。
ans = [-1 for _ in range(N-1)]

#vという頂点からpという親にcolorという色で繋がっている。
def dfs(v, color, p):
  k = 1 #色の初期値
  for i in range(len(g[v])): #vから繋がっている頂点をtoとして探す
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: #親は一つでそれ以外は子。親の時だけ無視すればよい。
      continue
    if k == color: #親から繋がっている色と被ったらダメ。
      k += 1
    ans[ID] = k
    k += 1 #ここで足す1をしないとこのfor loopの中の辺で色が被る。
    dfs(TO,ans[ID],v)

dfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)
import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[n]%mod)
calc()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[s]%mod)
calc()
l = []
while True:
  h,w = map(int,input().split())
  if (h,w) == (0,0):
    break
  else:
    l.append([h,w])
for i in l:
  r1 = ''
  r2 = ''
  for jin range(i[1]//2):
    r1 += '#.'
    r2 += '.#'
  if i[1]%2 == 1:
    r1 += '#'
    r2 += '.'
  for m in range(i[0]//2):
    print(r1)
    print(r2)
  if i[0]%2 == 1:
    print(r1)
  print()

### FIXED CODE ###

l = []
while True:
  h,w = map(int,input().split())
  if (h,w) == (0,0):
    break
  else:
    l.append([h,w])
for i in l:
  r1 = ''
  r2 = ''
  for j in range(i[1]//2):
    r1 += '#.'
    r2 += '.#'
  if i[1]%2 == 1:
    r1 += '#'
    r2 += '.'
  for m in range(i[0]//2):
    print(r1)
    print(r2)
  if i[0]%2 == 1:
    print(r1)
  print()
w, h, n = map(int, input().split())
a =[list(map(int, input().split())) for _ in range(n)]

g = [1*h]*w

for i in range(n):
  if a[i][2] == 1:
    g[:a[i][0]] = [0]*a[i][0]
  elif a[i][2] == 2:
    g[a[i][0]:] = [0]*a[i][0]
  elif a[i][2] == 3:
    g = [0 if g[j] == 0 else g[j]-a[i][1] for j in range(w)]
  elif a[i][2] == 4:
    g = [0 if g[j] == 0 else a[i][1] for j in range(w)]
    
  
print(sum(g))

### FIXED CODE ###

w,h,n = map(int,input().split())
p = [0,w,0,h]
for i in range(n):
    x,y,a = map(int,input().split())
    if a == 1:
        p[0] = max(x,p[0])
    if a == 2:
        p[1] = min(x,p[1])
    if a == 3:
        p[2] = max(y,p[2])
    if a == 4:
        p[3] = min(y,p[3])
print(max(0,p[1]-p[0])*max(0,p[3]-p[2]))
#c = [list(map(int,input().split())) for _ in range(5)]
c = [int(input()) for _ in range(5)]

last = 10

for i in range(5):
    if c[i] % 10 ==  0:
        continue
    else:
        if last > c[i] % 10:
            last = c[i] % 10
            idx = i
    
ans = 0


for i in range(5):
    if i == idx:
        ans = ans + c[i]
    else:
        if c[i] % 10 == 0:
            ans = ans + c[i]
        else:
            ans= ans + ( c[i] // 10 + 1 ) * 10


print(ans)

### FIXED CODE ###

c = [int(input()) for _ in range(5)]

last = 10

idx = 0

for i in range(5):
    if c[i] % 10 ==  0:
        continue
    else:
        if last > c[i] % 10:
            last = c[i] % 10
            idx = i
    
ans = 0


for i in range(5):
    if i == idx:
        ans = ans + c[i]
    else:
        if c[i] % 10 == 0:
            ans = ans + c[i]
        else:
            ans= ans + ( c[i] // 10 + 1 ) * 10


print(ans)
n = int(input().split())
a = n // 2 + n % 2
print(a)

### FIXED CODE ###

n = int(input())
a = n // 2 + n % 2
print(a)
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
node2set_id = defaultdict(int)
set_id2nodes = defaultdict(set)

# idxなどを振る
id_left = [i+1 for i in range(M)]
for i in range(M):
    x, y, z = list(map(int, input().split()))

    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        # x,yが所属するグループIDを振る
        node2set_id[x] = id
        node2set_id[y] = id

        # グループIDに対するセットを追加
        set_id2nodes[id] |= {x, y}

    elif node2set_id[x] * node2set_id[y] == 0:
        id = node2set_id[x] + node2set_id[y]
        node2set_id[x] = id
        node2set_id[y] = id
        set_id2nodes[id] |= {x, y}
    else:
        if node2set_id[x] - node2set_id[y] == 0:
            continue
        id = node2set_id[x]
        # yが所属するグループIDをすべてxのものに置き換える
        for y_idx in set_id2nodes[node2set_id[y]]:
            node2set_id[y_idx] = id
            set_id2nodes[id] |= {y_idx}
        set_id2nodes[node2set_id[y]] = {}

num = sum([len(m) - 1 for m in set_id2nodes.values()])

print(N-num)


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
node2set_id = defaultdict(int)
set_id2nodes = defaultdict(set)

# idxなどを振る
id_left = [i + 1 for i in range(M)]

for i in range(M):
    x, y, z = list(map(int, input().split()))

    # ともにIDが振られていないとき
    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        # x,yが所属するグループIDを振る
        node2set_id[x] = id
        node2set_id[y] = id

        # グループIDに対するセットを追加
        set_id2nodes[id] |= {x, y}

    # どちらか一方にのみIDが振られているとき(片方が0になる)
    elif node2set_id[x] * node2set_id[y] == 0:
        id = node2set_id[x] + node2set_id[y]
        node2set_id[x] = id
        node2set_id[y] = id
        set_id2nodes[id] |= {x, y}

    # 両方振られているとき
    else:
        # 同じIDならそもそも考える必要がない
        if node2set_id[x] - node2set_id[y] == 0:
            continue

        # 異なるグループのときにはマージする
        id = node2set_id[x]
        prev_y = node2set_id[y]

        # yが所属するグループIDをすべてxのものに置き換える
        for y_idx in set_id2nodes[node2set_id[y]]:
            node2set_id[y_idx] = id
            set_id2nodes[id] |= {y_idx}

        del set_id2nodes[prev_y]


num = sum([len(m)-1 for m in set_id2nodes.values()])

print(N - num)
N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v==i[0]:
      continue
    dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v!=i[0]:
      dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)
import sys
input = sys.stdin.readline
N = int(input())
pira = [[] for i in range(N)]
ans = [0,0,0]
a = False
for i in range(N):
	pira[i] = list(map(int, input().split()))
tmp = 0

for i in range(len(pira)):
	if pira[i][2] == 0:
		continue
	else:
		tmp = pira[i][2] + abs(pira[i][0]-x) + abs(pira[i][1]-y)

for x in range(101):
	for y in range(101):
		for i in range(1,len(pira)):
			if pira[i][2] == 0:
				continue
			if tmp != pira[i][2] + abs(pira[i][0]-x) + abs(pira[i][1]-y):
				a = False
				# ans = [0,0,0]
				break
			else:
				a = True
				ans = [x,y,tmp]
		if a:
			break
	if a:
		break

print(ans[0],ans[1],ans[2])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
pira = [[] for i in range(N)]
for i in range(N):
	pira[i] = list(map(int, input().split()))
	if pira[i][2] != 0:
		k = pira[i]

for x in range(101):
	for y in range(101):
		tmp = k[2] + abs(x-k[0]) + abs(y-k[1])
		for i in range(len(pira)):
			if pira[i][2] != max(tmp-abs(x-pira[i][0])-abs(y-pira[i][1]),0):
				break
			if i == len(pira)-1:
				print(x,y,tmp)
				exit()
a, b = input().split()
print(a * b)

### FIXED CODE ###

a, b = map(int, input().split())
print(a * b)
n, m = (int(i) for i in input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
a.sort()
bc.sort(key=lambda x:x[1], reverse=True)

print(a)
print(bc)

index = 0
break_flag = False

for i in range(m):
    for j in range(bc[i][0]):
        if(a[index] < bc[i][1] and index < n):
            a[index] = bc[i][1]
            index += 1
            print(a)
        else:
            break_flag = True
            break
    if  break_flag:
        break
print(sum(a))

### FIXED CODE ###

n, m = (int(i) for i in input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
a.sort()
bc.sort(key=lambda x:x[1], reverse=True)

# print(a)
# print(bc)

index = 0
break_flag = False

for i in range(m):
    for j in range(bc[i][0]):
        if (index < n):
            if(a[index] < bc[i][1]):
                a[index] = bc[i][1]
                index += 1
                # print(a)
            else:
                break_flag = True
                break
        else:
            break_flag = True
            break
    if  break_flag:
        break
print(sum(a))
N, L = map(int, input().split())
lix = sorted(input() for i in range(L))

print("".join(lix))

### FIXED CODE ###

N, L = map(int, input().split())
lix = sorted(input() for i in range(N))

res = "".join(lix)
print(res)
#!/usr/bin python3
# -*- coding: utf-8 -*-

n, k = map(int, input().split())
p = [int(i)-1 for i in input().split()]
c = list(map(int, input().split()))

rc = [0] * n
rp = [0] * n

for i in range(n):
    if rc[i]!=0:
        continue
    else:
        nw = set([i])
        np = c[i]
        nx = p[i]
        while not nx in nw:
            nw.add(nx)
            np += c[nx]
            nx = p[nx]
        cnt = len(nw)
        for x in nw:
            rc[x] = cnt
            rp[x] = max(0, np)
ret = - 10 ** 18
for i in range(n):
    pseq = [0]
    nx = p[i]
    for j in range(1,rc[i]+1):
        pseq.append(pseq[-1]+c[nx])
        nx = p[nx]
    pseq = pseq[1:]
    if k <= rc[i]:
        ret = max(ret, max(pseq[:k]))
    elif rp[i] < 0:
        ret = max(ret, max(pseq))
    else:
        tmp = max(pseq)
        tmp = max(tmp, rp[i] + max(pseq[:k%rc[i]]))
        tmp += rp[i]*(k//rc[i]-1)
        ret = max(ret, tmp)
print(ret)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

n, k = map(int, input().split())
p = [int(i)-1 for i in input().split()]
c = list(map(int, input().split()))

ret = - 10 ** 18
for s in range(n):
    nxt = p[s]
    S = [c[nxt]]
    while nxt != s:
        nxt = p[nxt]
        S.append(S[-1]+c[nxt])

    if k<=len(S):
        pt = max(S[:k])
    else:
        if S[-1] <= 0:
            pt = max(S)
        else:
            pt = max(S)
            if k%len(S)!=0:
                pt = max(pt, S[-1]+max(S[:k%len(S)]))
            pt += S[-1]*(k//len(S)-1)
    ret = max(ret, pt)
print(ret)