Harryxun/stf_run huggingface dataset:
INF = float('inf')
N,M = map(int,input().split())
edge = []
d = [INF]*N
d[0] = 0
negative = [False for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,-c])

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        d[edge[j][1]] = min(d[edge[j][1]],d[edge[j][0]]+edge[j][2])

ans = d[N-1]

for i in range(N):
    for j in range(M):
        if d[j]==INF:
            continue
        if d[edge[j][1]]>d[edge[j][0]]+edge[j][2]:
            d[edge[j][1]]=d[edge[j][0]]+edge[j][2]
            negative[edge[j][1]] = True
        if negative[edge[j][0]]:
            negative[edge[j][1]] = True
print('inf' if negative[N-1] else -ans)


### FIXED CODE ###

INF = float('inf')
N,M = map(int,input().split())
edge = []
d = [INF]*N
d[0] = 0
negative = [False for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,-c])

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        d[edge[j][1]] = min(d[edge[j][1]],d[edge[j][0]]+edge[j][2])

ans = d[N-1]

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        if d[edge[j][1]]>d[edge[j][0]]+edge[j][2]:
            d[edge[j][1]]=d[edge[j][0]]+edge[j][2]
            negative[edge[j][1]] = True
        if negative[edge[j][0]]:
            negative[edge[j][1]] = True
print('inf' if negative[N-1] else -ans)
N = int(input())
def factorize(n, already):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+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])

    ret = []
    for a, b in arr:
        for i in range(1, b+1):
            ret.append(a*i)

    ret = set(ret) - set(already)
    return sorted(list(ret))[0]

already = []
z = 0
n = N
ans = 0
while n >= z:
    z = factorize(n, already)
    n = n // z
    already.append(z)
    ans += 1
    if n == 1:
        break
print(ans)


### FIXED CODE ###

N = int(input())
def factorize(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+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

if N == 1:
    print(0); exit()

f = factorize(N)
ans = 0
for p, i in f:
    j = 0
    while i > j:
        j += 1
        i -= j
        ans += 1
print(ans)
def ghke(k, x):
    return k * 500 >= x

if __name__ == "__main__":
    import sys
    in_str = []
    for line in sys.stdin:
        in_str.append(int(line))
    roundone([int(_) for _ in in_str[0].split()])

### FIXED CODE ###

def ghke(k, x):
    print('Yes') if k * 500 >= x else print("No")

if __name__ == "__main__":
    import sys
    in_str = []
    for line in sys.stdin:
        in_str.append(line)
    k, x = [int(_) for _ in in_str[0].split(' ')]
    ghke(k, x)
N = int(input())
C = {i:0 for i in range(20)}
A = input().split()
for i in range(N):
    a = bin(int(A[i]))[2:]
    n = len(a)
    for j in range(n):
        if a[j]=="1":
            C[n-1-j] += 1
cnt = 0
for i in range(20):
    if C[i]>0:
        cnt += C[i]*(N-C[i])*2**i
print(cnt)

### FIXED CODE ###

p = 10**9+7
N = int(input())
C = {i:0 for i in range(60)}
A = input().split()
for i in range(N):
    a = bin(int(A[i]))[2:]
    n = len(a)
    for j in range(n):
        if a[j]=="1":
            C[n-1-j] += 1
cnt = 0
for i in range(60):
    if C[i]>0:
        cnt = (cnt+C[i]*(N-C[i])*2**i)%p
print(cnt)
a,b = map(float, raw_input().split())
d = (int) (a/b)
r = (int) (a%b)
f = float (a/b)

print({0} {1} {2:6f}.format(d,r,f))

### FIXED CODE ###

a,b = map(float, raw_input().split())
d = (int) (a/b)
r = (int) (a%b)
f = float (a/b)

print("{0} {1} {2:6f}".format(d,r,f))
a=''.join(list(sorted(list(map(int,input().split())))))
if(a=='1479'):
	print('YES')
else:
	print('NO')




### FIXED CODE ###

a=''.join(list(sorted(list(input().split()))))
if(a=='1479'):
	print('YES')
else:
	print('NO')
x**3


### FIXED CODE ###

number = int(input())
print(number**3)
n = int(intput())
A = list(map(int,input().split()))
B = A.sorted()
dif = 0
for i in range(n):
  if A[i]!=B[i]:
    dif+=1
if dif==0 or dif==2:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
B = sorted(A)
dif = 0
for i in range(n):
  if A[i]!=B[i]:
    dif+=1
if dif==0 or dif==2:
  print("YES")
else:
  print("NO")
N = int(input())
A = list(map(int, input().split()))
AA = [0] * (N)
for i in range(N):
    AA[i] = list(format(A[i], 'b'))

ans = [0] * 20
for i in range(N):
    AA[i].reverse()
    for j in range(len(AA[i])):
        ans[j] += int(AA[i][j])

ret = []
for i in range(N):
    temp = 0
    for j in range(len(AA[i])):
        if (ans[j] - int(AA[i][j])) % 2 == 1:
            temp += 1 << j

    ret.append(temp)

print(*ret)

### FIXED CODE ###

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

AA = [0] * (N)
for i in range(N):
    AA[i] = list(format(A[i], 'b').zfill(42))

ans = [0] * 42
ma = 0
for i in range(N):
    AA[i].reverse()
    for j in range(len(AA[i])):
        ma = max(ma, j)
        ans[j] += int(AA[i][j])

ret = []
for i in range(N):
    temp = 0
    for j in range(ma):
        if (ans[j] + int(AA[i][j])) & 1 == 1:
            temp += 1 << j

    ret.append(temp)

print(*ret)
H,W,K=map(int,input().split())
S=[input() for i in range(H)]
P=[[0 for i in range(W)] for m in range(H)]

for h in range(H):
    if "#" in S[h]:
        front=h
        break


m=0
x=0
for w in range(W):
    if S[front][w]=="#":
        m+=1
        for z in range(x,w+1):
            P[front][z]=m
        x=w+1
for z in range(x,W):
    P[front][z]=m

for h in range(front-1,-1,-1):
    for m in range(M):
        P[h][m]=S[h+1][m]


for h in range(front+1,H):
    if "#" in S[h]:
        x=0
        for w in range(W):
            if S[h][w]=="#":
                m+=1
                for z in range(x,w+1):
                    P[h][z]=m
                x=w+1
        for z in range(x,W):
            P[h][z]=m
    else:
        for w in range(W):
            P[h][w]=S[h-1][w]

for h in range(H):
    print(" ".join(list(map(str,P[h]))))


### FIXED CODE ###

H,W,K=map(int,input().split())
S=[input() for i in range(H)]
P=[[0 for i in range(W)] for m in range(H)]

for h in range(H):
    if "#" in S[h]:
        front=h
        break


m=0
x=0
for w in range(W):
    if S[front][w]=="#":
        m+=1
        for z in range(x,w+1):
            P[front][z]=m
        x=w+1
for z in range(x,W):
    P[front][z]=m

for h in range(front-1,-1,-1):
    for w in range(W):
        P[h][w]=P[h+1][w]


for h in range(front+1,H):
    if "#" in S[h]:
        x=0
        for w in range(W):
            if S[h][w]=="#":
                m+=1
                for z in range(x,w+1):
                    P[h][z]=m
                x=w+1
        for z in range(x,W):
            P[h][z]=m
    else:
        for w in range(W):
            P[h][w]=P[h-1][w]

for h in range(H):
    print(" ".join(list(map(str,P[h]))))
s=[input() for _ in range(int(input()))]
t=[input() for _ in range(int(input()))]
cnt=[0]*(len(s)+1)
for i in range(len(s)):
    cnt[i]=s.count(s[i])-t.count(t[i])
print(max(cnt))



### FIXED CODE ###

s=[input() for _ in range(int(input()))]
t=[input() for _ in range(int(input()))]
cnt=[0]*(len(s)+1)
for i in range(len(s)):
    cnt[i]=s.count(s[i])-t.count(s[i])
print(max(cnt))
import numpy as np
N,K = map(int,input().split())
q = list(map(int,input().split()))
q = np.array(q)

p = (q + 1) /2
p = p.tolist()
a = sum(p[:K])
mx = a

for i in range(0,N-K):
    a = a - p[i] + p[i+K]
    if a > mx:
        mx = a

print(float(mx))

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
q = list(map(int,input().split()))
q = np.array(q)

p = (q + 1) /2
p = p.tolist()
a = sum(p[:K])
mx = a

for i in range(0,N-K):
    a = a - p[i] + p[i+K]
    if a > mx:
        mx = a

print(mx)
import sys
#from math import sqrt, floor, factorial, gcd
#from collections import deque, Counter, defaultdict
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def is_prime(n):
	for i in range(2, int(sqrt(n))+1):
		if n%i == 0:
			return(False)
	return(True)

def func(n, arr):
	dic = {}
	if is_prime(n):
		return(arr[-1]+min(func(n, arr)))
def factorize(n):
	output = []
	for i in range(2, int(sqrt(n))+1):
		if n%i == 0:
			c = 0
			while n%i == 0:
				n //= i
				c += 1
			output.append((i, c))
	if n > 1:
		output.append((n, 1))
	return(output)


def func(arr, n):
	if n == 1:
		return(abs(arr[n]-arr[n-1]))
	if n== 0:
		return(0)
	return(min(abs(arr[n]-arr[n-1])+func(arr,n-1), abs(arr[n]-arr[n-2])+func(arr,n-2))) 

def a():
	n = int(inp()); arr = read()
	dic = {}
	def func(arr, n):
		if n == 1:
			return(abs(arr[n]-arr[n-1]))
		if n== 0:
			return(0)
		if n in dic:
			return(dic[n])
		min_path = min(abs(arr[n]-arr[n-1])+func(arr,n-1), abs(arr[n]-arr[n-2])+func(arr,n-2))
		dic[n] = min_path
		return(min_path) 


	print(func(arr, n-1))




if __name__ == "__main__":
	a()

### FIXED CODE ###

import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def a():
	n = int(inp()); arr = read()
	dp = [0 for i in range(n)]
	dp[0] = 0
	dp[1] = abs(arr[1]-arr[0])
	for i in range(2, n):
		dp[i] = min(dp[i-1]+abs(arr[i]-arr[i-1]), dp[i-2]+abs(arr[i]-arr[i-2]))
	print(dp[n-1])




if __name__ == "__main__":
	a()
n=int(input())
a=list(map(int,input().split()))
a.sort()
negative=[]
positive=[]
for ele in a:
    if ele<0:
        negative.append(ele)
    else:
        positive.append(ele)
if len(negative)==0:
    print(sum(a))
else:
    if len(negative)%2==0:
        print(-sum(negative)+sum(positive))
    else:
        if -negative.back()>positive[0]:
            print(-sum(negative)+sum(positive[1:])-positive[0])
        else:
            print(-sum(negative[:-2])+sum(positive)+negative.back())


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
negative=[]
positive=[]
for ele in a:
    if ele<0:
        negative.append(ele)
    else:
        positive.append(ele)
if len(negative)==0:
    print(sum(a))
else:
    if len(negative)%2==0:
        print(-sum(negative)+sum(positive))
    else:
        if len(positive)==0:
            print(-sum(negative)+2*negative[-1])
        elif -negative[-1]>positive[0]:
            print(-sum(negative)+sum(positive[1:])-positive[0])
        else:
            print(-sum(negative[:-1])+sum(positive)+negative[-1])
import copy

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

for i in range(N):
    k=i+1
    B = copy.copy(A)
    B.pop(i)
    C = [0]*(N-1)
    for l in range(N-1):
        C[B[l]] += 1
    temp = 0
    for m in range(N-1):
        temp += int(C[m]*(C[m]-1)/2)
    print(temp)

### FIXED CODE ###

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

B = [0]*(N+1)
for l in range(N):
    B[A[l]] += 1
ans = 0
for i in range(N+1):
    ans += int(B[i] * (B[i]-1) / 2)
for k in range(N):
        print(ans - B[A[k]] + 1)
n,m=map(int,input().split())
a=[]
for _ in range(n):
  _,*b=map(int,input().split())
  a+=b
print(sum(n==a.count i+1for i in range(m)))

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for _ in range(n):
  _,*b=map(int,input().split())
  a+=b
print(sum(n==a.count(i+1)for i in range(m)))
from sys import stdin

def solve(N, xys):
    diff = []
    diff_count = []
    idx = 0
    for i in range(N-1):
        for j in range(i+1,N):
            tmp_a = [xys[i][0] - xys[j][0], xys[i][1] - xys[j][1]]
            tmp_b = [xys[j][0] - xys[i][0], xys[j][1] - xys[i][1]]
            if tmp_a in diff:
                diff_count[diff.index(tmp_a)] += 1
            elif tmp_b in diff:
                diff_count[diff.index(tmp_b)] += 1
            else:
                diff.append(tmp_a)
                diff_count.append(1)
                idx += 1
    return N - max(diff_count)

if __name__ == '__main__':
    N = int(stdin.readline().rstrip())
    xys = []
    for i in range(N):
        xys.append([int(x) for x in stdin.readline().rstrip().split()])
    print(solve(N, xys))


### FIXED CODE ###

from sys import stdin

def solve(N, xys):
    diff = []
    diff_count = []
    idx = 0
    for i in range(N-1):
        for j in range(i+1,N):
            tmp_a = [xys[i][0] - xys[j][0], xys[i][1] - xys[j][1]]
            tmp_b = [xys[j][0] - xys[i][0], xys[j][1] - xys[i][1]]
            if tmp_a in diff:
                diff_count[diff.index(tmp_a)] += 1
            elif tmp_b in diff:
                diff_count[diff.index(tmp_b)] += 1
            else:
                diff.append(tmp_a)
                diff_count.append(1)
                idx += 1
    if diff == []:
        diff_count.append(0)
    return N - max(diff_count)

if __name__ == '__main__':
    N = int(stdin.readline().rstrip())
    xys = []
    for i in range(N):
        xys.append([int(x) for x in stdin.readline().rstrip().split()])
    print(solve(N, xys))
N,K = list(map(int,input().split()))
S = list(input())
S[K-1]．lower()
print("".join(S))

### FIXED CODE ###

N,K = list(map(int,input().split()))
S = list(input())
S[K-1]=S[K-1].swapcase()
print("".join(S))
c=[]
a,b=map(int,input().split())
c[0]=a
c[1]=b


for i in range(2):
  
  d+=max(c)
  max(c)=d-1
print(d)

### FIXED CODE ###

a,b=map(int,input().split())
c=0
for i in range(2):
  if a>=b:
    c+=a
    a-=1
  else:
    c+=b
    b-=1
print(c)
from copy import deepcopy
from collections import deque
from itertools import chain

dire = [(0,1),(1,0),(0,-1),(-1,0)]

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
S_initial = deepcopy(S)

    
def bfs():
    S[0][0] = "#"
    dq = deque() ## (y, x, dist from start)
    dq.append((0,0,0))
    while dq:
        y,x,d = dq.popleft()
        for dy,dx in dire:
            ny = y + dy; nx = x + dx
            if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
                continue
            if (ny,nx) == (H-1,W-1):
                return d+1
            if S[ny][nx] == ".":
                dq.append((ny,nx,d+1))
                S[ny][nx] = "#"

dist = bfs()
S_flatten = list(chain.from_iterable(S_initial))
cnt_dot = S_flatten.count('.') - (dist+1)
print(cnt_dot)



### FIXED CODE ###

from copy import deepcopy
from collections import deque
from itertools import chain

dire = [(0,1),(1,0),(0,-1),(-1,0)]

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
S_initial = deepcopy(S)

    
def bfs():
    S[0][0] = "#"
    dq = deque() ## (y, x, dist from start)
    dq.append((0,0,0))
    while dq:
        y,x,d = dq.popleft()
        if d > H*W:
          break
        for dy,dx in dire:
            ny = y + dy; nx = x + dx
            if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
                continue
            if (ny,nx) == (H-1,W-1):
                return d+1
            if S[ny][nx] == ".":
                dq.append((ny,nx,d+1))
                S[ny][nx] = "#"
    return -1

dist = bfs()
if dist == -1:
  print(-1)
else:
  S_flatten = list(chain.from_iterable(S_initial))
  cnt_dot = S_flatten.count('.') - (dist+1)
  print(cnt_dot)
_ = input()
an = sorted([int(i) for i in input().split(" ")])

dic = {}
for a in an:
    if a not in dic:
        dic[a] = 0
    dic[a] += 1

tim = 0
for a in dic:
    if dic[1] % 2 == 0:
        tim += 1

print(len(dic)-(tim+1)%2)

### FIXED CODE ###

import collections

_ = input()
an = sorted([int(i) for i in input().split(" ")])

c = collections.Counter(an)

print(len(c)-(len(c)+1)%2)
n = int(input())
A = sorted(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))

def rec(i, sum, m):
    if sum == m:
        return True
    elif sum > m:
        return False

    if i >= n:
        return False

    rst = rec(i+1, sum, m) or rec(i+1, sum + A[i], m)
    return rst

for m in M:
    if rec(0, 0, m):
        print('yes')
    else:
        print('no')


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))

# 上限と下限でフィルター
max_A = 0
min_A = float('inf')
for num in A:
    max_A += num
    if num < min_A:
        min_A = num

def rec(i, m):
    if m < 0:
        return False
    elif m == 0:
        return True
    if i >= n:
        return False

    rst = rec(i+1, m - A[i]) or rec(i+1, m)
    return rst

for m in M:
    if m < min_A or max_A < m:
        print('no')
    elif rec(0, m):
        print('yes')
    else:
        print('no')
n = int(input())
a = int(input())
b = int(input())

if n == 1:
  print('Hello World')
else:
  print(a+b)

### FIXED CODE ###

n = int(input())

if n == 1:
  print('Hello World')
else:
  a = int(input())
  b = int(input())
  print(a+b)
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(r):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1[r][b] %= mod
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans*6%mod)


### FIXED CODE ###

from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for b in range(max(1,g))] for g in range(max(1,r))] for r in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(max(1,r)):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][r][g] >= 0:
        dp[r+1][r][g] += v
        dp[r+1][r][g] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans%mod)
N = int(input())
number = []
    for A in range(1,10):
        for B in range(1,10):
            number.append(A*B)
if N in number :
    print("Yes")
else :
    print("No")

### FIXED CODE ###

N = int(input())
number = []
for a in range(1,10):
    for b in range(1,10):
        number.append(b*a)
if N in number :
    print("Yes")
else :
    print("No")
import math, sys
X = int(input())
for a in range(-200,200):
  a5 == a**5
  for b in range(-200,200):
    if a5-b**5==X:
      print(str(a)+" "+str(b))
      sys.exit()

### FIXED CODE ###

import math, sys
X = int(input())
for a in range(-200,200):
  a5 = a**5
  for b in range(-200,200):
    if a5-b**5==X:
      print(str(a)+" "+str(b))
      sys.exit()
a, b = map(int, input().split())
s = input()
flg = 0
for i in range(a +b):
    if not(0 <= int(s[i]) <= 9): 
        if s[a] == "-":
            flg = 1
        
print("Yes" if flg == 1 else "No")

### FIXED CODE ###

a, b = map(int, input().split())
s = input()
flg = 0
for i in range(a +b +1):
    try:
        if (0 <= int(s[i]) <= 9):
            if i == a:
                flg = 0
                break
    except:
        if i == a:
            flg = 1
        else:
            flg = 0
            break
print("Yes" if flg == 1 else "No")
a,b = map(int,input().split())
c,d = map(int,input().split())
print(a*b-c-d+cd)

### FIXED CODE ###

a,b = map(int,input().split())
c,d = map(int,input().split())
print(a*b-c*b-d*a+c*d)
import sys
from collections import defaultdict

input = sys.stdin.readline

N = int(input())
G = defaultdict(list)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append((v - 1, w))
    G[v - 1].append((u - 1, w))
res = [None] * N


def dfs(v, c):
    res[v] = c
    for u, w in G[v]:
        if res[u] is not None:
            continue
        if w % 2 == 0:
            dfs(u, c)
        else:
            dfs(u, 1 - c)


dfs(0, 0)
for x in res:
    print(x)


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(100000)
input = sys.stdin.readline

N = int(input())
G = defaultdict(list)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append((v - 1, w))
    G[v - 1].append((u - 1, w))
res = [None] * N


def dfs(v, c):
    res[v] = c
    for u, w in G[v]:
        if res[u] is not None:
            continue
        if w % 2 == 0:
            dfs(u, c)
        else:
            dfs(u, 1 - c)


dfs(0, 0)
for x in res:
    print(x)
x, y = map(int,input().split())
if x < y:
  print("<")

elif x == y:
  print("=")
  
else:
  print(">")

### FIXED CODE ###

x, y = input().split()
if x < y:
  print("<")
 
elif x == y:
  print("=")
  
else:
  print(">")
str = input().split()
v=""
sa=list()
for i in range(int(str[1])):
   sa.append(input().strip())
sa.sort()
for i in sa:
    v=v+i

print(v)

### FIXED CODE ###

str = input().split()
v=""
sa=list()
for i in range(int(str[0])):
    sa.append(input()[:int(str[1])])
sa.sort()
for i in sa:
    v=v+i

print(v)
n = int(input())
c = [-1,-1,-1]
a = 1
for i in map(int,input().split()):
  a = a * c.count(i-1) % 1000000007
  c[c.index(i-1)] = i
print(a)

### FIXED CODE ###

n = int(input())
c = [-1,-1,-1]
a = 1
for i in map(int,input().split()):
  co = c.count(i-1)
  if co == 0:
    print(0)
    exit()
  a = a * co % 1000000007
  c[c.index(i-1)] = i
print(a)
n = int(input())
for i in range(n+1):
    d[i] = int(input())
ans = len(set(d))
print(ans)


### FIXED CODE ###

n = int(input())
d = []
for i in range(n):
    d.append(int(input()))
ans = len(set(d))
print(ans)
from statistics import *
while True:
    n = int(input())
    if(n == 0): break
    data = list(map(int,input().split()))    
    elif(n == 1):
        print("%.10f" %0)
    else:
        print(stdev(data))


### FIXED CODE ###

from math import *
while True:
    n = int(input())
    if(n == 0 ): break
    data = list(map(int,input().split()))  
    a = sum(data) / n
    b = 0
    c = 0
    for i in data:
        b += pow(i-a,2)
    c = sqrt(b/n)
    
    print(c)
import sympy as sym

a, b = map(int, input().split())
print(len(set(sym.primefactors(a)) & set(sym.primefactors(b))) + 1)

### FIXED CODE ###

def primeFact(n):
    i = 2
    pl = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            pl.append(i)
        i += 1
    if n > 1:
        pl.append(int(n))
    return pl


a, b = map(int, input().split())
print(len(set(primeFact(a)) & set(primeFact(b))) + 1)