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

from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
  u, v, w = map(int, input().split())
  graph[u].append((v, w))
  graph[v].append((u, w))
  
parent = [0] * (n+1)
ans = [0] * (n+1)

q = deque([1])
while q:
  x = q.popleft()
  for y, w in graph[x]:
    if(parent[y] == x):
      continue
    else:
      parent[y] = x
      ans[y] = ans[x]^(w&1)
      q.append(y)
      
for i in range(1, n+1):
  print(ans[i])
      



### FIXED CODE ###

from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
  u, v, w = map(int, input().split())
  graph[u].append((v, w))
  graph[v].append((u, w))
  
parent = [0] * (n+1)
ans = [0] * (n+1)

q = deque([1])
while q:
  x = q.popleft()
  for y, w in graph[x]:
    if(y == parent[x]):
      continue
    parent[y] = x
    ans[y] = ans[x]^(w&1)
    q.append(y)
      
for i in range(1, n+1):
  print(ans[i])
### BUGGY CODE ###

import bisect
import sys
if __name__ == '__main__':
    n = int(input())
    s = list(input())
    r = 0
    g = 0
    b = 0
    for i in s:
        if i == "R":
            r += 1
        elif i == "G":
            g += 1
        else:
            b += 1
    ans = r * g * b
    for i in range(n):
        for j in range(i, n):
            out = j * 2 - i
            if out >= n:
                continue
            if len({s[i], s[j], s[out]}) == 3:
                ans -= 1
    print(ans)


### FIXED CODE ###

import sys

if __name__ == '__main__':
    input = sys.stdin.readline
    n = int(input())
    s = list(input())
    s.remove('\n')
    r = 0
    g = 0
    b = 0
    for i in s:
        if i == "R":
            r += 1
        elif i == "G":
            g += 1
        else:
            b += 1
    ans = r * g * b
    for i in range(n):
        for j in range(i, n):
            out = j * 2 - i
            if out >= n:
                continue
            if len({s[i], s[j], s[out]}) == 3:
                ans -= 1
    print(ans)
### BUGGY CODE ###

from collections import deque
import heapq
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e = sorted(e)
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False
### BUGGY CODE ###

K,S = map(int,input().split())
count = 0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k ==S :
        count +=1
      
print(count)

### FIXED CODE ###

K,S = map(int,input().split())
count = 0
for i in range(K+1):
  for j in range(K+1):
    if i+j <= S and i+j+K >= S:
      count +=1
      
print(count)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

# T = defaultdict(list)
T = [set() for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int, input().split())
    # T[x] += [y]
    # T[y] += [x]
    T[x].add(y)
    T[y].add(x)

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD) 



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

# T = defaultdict(list)
T = [set() for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int, input().split())
    # T[x] += [y]
    # T[y] += [x]
    T[x].add(y)
    T[y].add(x)

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)
### BUGGY CODE ###

while 1:
    a = list(input())
    if a == ["0", "0", "0", "0"]:break
    if a[0] == a[1] == a[2] == a[3]:print("NA")
    else:
        c = 0
        while 1:
            if a == ["6", "1", "7", "4"]:break
            c += 1
            s = int("".join(sorted(a)))
            l = int("".join(sorted(a, reverse = True)))
            a = list(str(l - s))
        print(c)


### FIXED CODE ###

while 1:
    a = list(input())
    if a == ["0", "0", "0", "0"]:break
    if a[0] == a[1] == a[2] == a[3]:print("NA")
    else:
        c = 0
        while 1:
            if a == ["6", "1", "7", "4"]:break
            c += 1
            s = int("".join(sorted(a)))
            l = int("".join(sorted(a, reverse = True)))
            a = list("{:04d}".format(l - s))
        print(c)
### BUGGY CODE ###

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]

ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]

i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())

ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]

def main(N, Q, S, lrs):
    acindex = []
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            acindex.append(i)
    for l, r in lrs:
        count = 0
        for i in acindex:
            if l-1 <= i and i <= r-2:
                count += 1
        print(count)


N, Q = i2nn()
S = i2s()
lr = ss2nnn(ii2ss(Q))
main(N, Q, S, lr)


### FIXED CODE ###

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]

ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]

i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())

ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]

def main(N, Q, S, lrs):
    S2 = [0] * (N)
    for i in range(1, N):
        if S[i-1] == 'A' and S[i] == 'C':
            S2[i] = S2[i-1] + 1
        else:
            S2[i] = S2[i-1]
    for l, r in lrs:
        count = S2[r-1] - S2[l-1] 
        print(count)

N, Q = i2nn()
S = i2s()
lr = ss2nnn(ii2ss(Q))
main(N, Q, S, lr)
### BUGGY CODE ###

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6 + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

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

if X % 3 !=0 or X % 3 != 0:
    print(0)
    exit()

A = (2*Y - X) // 3
B = (2*X - Y) // 3

print(cmb(A+B, A, mod))


### FIXED CODE ###

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

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9 + 7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, N +1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if ((X + Y) % 3 != 0):
    print(0)
    exit()

A = (2 * Y - X) // 3
B = (2 * X - Y) // 3

print(cmb(A + B, A))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  a=tuple(int(input()) for _ in range(m))
  mod=10**9+7
  pattern=[0]*(n+1)
  pattern[0]=pattern[1]=1
  if 1 in a:
      pattern[1]=0
  for i in range(2,n+1):
      if i in a:
          pattern[i]=0
      else:
          pattern[i]=(pattern[i-1]+pattern[i-2])%mod
  print(pattern[n])
main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  a=tuple(int(input()) for _ in range(m))
  a=set(a)
  mod=10**9+7
  pattern=[0]*(n+1)
  pattern[0]=pattern[1]=1
  if 1 in a:
      pattern[1]=0
  for i in range(2,n+1):
      if i in a:
          pattern[i]=0
      else:
          pattern[i]=(pattern[i-1]+pattern[i-2])%mod
  print(pattern[n])
main()
### BUGGY CODE ###

L = list(map(int, input().split()))

N = L[0]
K = L[1]
Q = L[2]

A = []

for _ in range(Q):
    A.append(int(input()))
	
P = [K] * N


r = 0

for i in range(0,len(A)):
	r = A[i] - 1
	P[r] += 1
	P = list(map(lambda x: x-1,P))
	
for i in range(0,len(P)):
	if P[i] > 0:
		print("Yes")
	else:print("No")

### FIXED CODE ###

N,K,Q = map(int, input().split())

P = [0] * N


for i in range(Q):
	A = int(input())
	P[A-1] += 1


for j in range(0,len(P)):
	if K - Q + P[j] > 0:
		print('Yes')
	else:
		print('No')
### BUGGY CODE ###

from fractions import gcd
import itertools
k = int(input())

result = 0

# 3つとも等しい数字
for i in range(1, k+1):
    result += i

# 2つが等しくて、1つが異なる数字
for set in list(itertools.combinations(range(1, k+1), 2)):
    result += (gcd(set[0], set[1]))*6

# 3つとも異なる
for set in list(itertools.combinations(range(1, k+1), 3)):
    result += (gcd(gcd(set[0], set[1]), set[2]))*6

print(result)

### FIXED CODE ###

from math import gcd
k = int(input())
result = 0

# 3つとも等しい数字
for i in range(1, k+1):
    for j in range(i, k+1):
        for m in range(j, k+1):
            if i==j==m:
                result += i
            elif i==j or j==m:
                result += gcd(i, m)*3
            else:
                result += gcd(i, gcd(j,m))*6
print(result)
### BUGGY CODE ###

def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    dpi = dp[0]
    for dpi1, a in zip(dp[1:],a_s[:-1]):
        dpi1[0] = s = dpi[0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
        dpi=dpi1
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(k, a_s))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

p = []
m = []
zero = 0
for i in range(N) :
  if A[i] > 0 :
    p.append(A[i])
  elif A[i] < 0 :
    m.append(-A[i])
  else :
    zero += 1

p.sort()
m.sort()

ng, ok = -(10 ** 30), 10 ** 30
while ok - ng > 1 :
  mid = (ok + ng) // 2
  s = 0
    
  if mid < 0 :
    for i in range(len(m)) :
      x = (-mid+m[i]-1) // (m[i])
      s += len(p) - bisect_left(p, x)
    
  if mid >= 0 :
    for i in range(len(p)) :
      x = mid // p[i]
      s += max(0, bisect_left(p, x + 1) - 1 - i)
    for i in range(len(m)) :
      x = mid // m[i]
      s += max(0, bisect_left(m, x + 1) - 1 - i)
    s += (len(p) + len(m)) * zero
    s += len(p) * len(m)
    s += zero * (zero - 1) // 2
  
  if s < K :
    ng = mid
  else :
    ok = mid
    
print(ok)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

p = []
m = []
zero = 0
for i in range(N) :
  if A[i] > 0 :
    p.append(A[i])
  elif A[i] < 0 :
    m.append(-A[i])
  else :
    zero += 1

p.sort()
m.sort()

ng, ok = -(10 ** 18)-1, 10 ** 18+1
while ok - ng > 1 :
  mid = (ok + ng) // 2
  s = 0 
  if mid < 0 :
    j = 0
    for i in range(len(m) - 1, -1, -1) :
      while j < len(p) and m[i] * p[j] < -mid :
        j += 1
      s += len(p) - j
      
  else :
    j = len(p) - 1
    for i in range(len(p)) :
      while j >= 0 and p[i] * p[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    j = len(m) - 1
    for i in range(len(m)) :
      while j >= 0 and m[i] * m[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    s += (len(p) + len(m)) * zero + len(p) * len(m) + zero * (zero - 1) // 2

  if s < K :
    ng = mid
  else :
    ok = mid
    
print(ok)
### BUGGY CODE ###

a, b, c, k=input().split()
a=int(a)
b=int(b)
c=int(c)
k=int(k)
ans=0

while a>0 and k>0:
  ans+=1
  a+=-1
  k+=-1

while b>0 and k>0:
  b+=-1
  k+=-1

while c>0 and k>0:
  ans+=-1
  c+=-1
  k+=-1
  
print(ans)

### FIXED CODE ###

a, b, c, k=input().split()
a=int(a)
b=int(b)
c=int(c)
k=int(k)
ans=0

if a>0 and k>0 and a<=k:
  k=k-a
  ans=ans+a
elif a>0 and k>0 and a>k:
  ans=ans+k
  k=0

if b>0 and k>0 and b<=k:
  k=k-b
elif b>0 and k>0 and b>k:
  k=0
  
if c>0 and k>0 and c<=k:
  k=k-c
  ans=ans-c
elif c>0 and c>0 and c>k:
  ans=ans-k
  k=0

  
print(ans)
### BUGGY CODE ###

import collections
import math
 
def combinations_count(n, r):
  if n == r:
    return 1
  elif n < r:
    return 0
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
combi_count = {}
total = 0
for k, v in combi.items():
  combi_count[k] = combinations_count(v, 2)
  total += combi_count[k]

for i in range(N):
  ans = total - combi_count[A[i]] + combinations_count(combi[A[i]]-1, 2)
  print(ans)

### FIXED CODE ###

import collections
import math
 
def combinations_count(n, r):
  if n == r:
    return 1
  elif n < r:
    return 0
  else:
    return n * (n-1) // 2 
    #math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
combi_count = {}
calc_dict = {}
total = 0
for k, v in combi.items():
  if v in calc_dict:
    combi_count[k] = calc_dict[v]
  else:
    combi_count[k] = combinations_count(v, 2)
    calc_dict[v] = combi_count[k]
  total += combi_count[k]

for i in range(N):
  ans = total - combi_count[A[i]] + combinations_count(combi[A[i]]-1, 2)
  print(ans)
### BUGGY CODE ###

import bisect
import heapq
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
a_left = sorted(a[:N])
a_right = sorted(a[N:])
sum_left = sum(a_left)
sum_right = sum(a_right[:N])
res = sum_left - sum_right

heapq.heapify(a_left)

len_left = N
for elem in a[N:2*N]:
    le = bisect.bisect_left(a_right, elem)
    a_right[le:] = a_right[le+1:]
    if le < N:
        sum_right -= elem
        sum_right += a_right[N-1]
    now = heapq.heappop(a_left)
    if now < elem:
        heapq.heappush(a_left, elem)
        sum_left += (elem-now)
    else:
        heapq.heappush(a_left, now)
    res = max(res, sum_left-sum_right)
print(res)


### FIXED CODE ###

import bisect
import heapq
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
a_left = sorted(a[:N])
a_right = sorted(a[2*N:])
sum_left = sum(a_left)
sum_right = sum(a_right)
#res = sum_left - sum_right
res = sum_left - sum(sorted(a[N:])[:N])
a_right = [-elem for elem in a_right]
heapq.heapify(a_right)
heapq.heapify(a_left)
sr = [0]*(N+1)
sr[0] = sum_right

for i,elem in enumerate(reversed(a[N:2*N])):
    now = -heapq.heappop(a_right)
    if now > elem:
        heapq.heappush(a_right, -elem)
        sum_right += (elem-now)
    else:
        heapq.heappush(a_right, -now)
    sr[i+1] = sum_right

for i,elem in enumerate(a[N:2*N]):
    now = heapq.heappop(a_left)
    if now < elem:
        heapq.heappush(a_left, elem)
        sum_left += (elem-now)
    else:
        heapq.heappush(a_left, now)
    res = max(res, sum_left-sr[N-i-1])
print(res)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
maxA_len = len(bin(maxA)[2:])
num0_each_digit = [0 for _ in range(maxA_len)]
num1_each_digit = [0 for _ in range(maxA_len)]

for i in range(N):
    for i_bit, bit in enumerate(bin(A[i])[2:].zfill(maxA_len)):
        if bit == '0':
            num0_each_digit[i_bit] += 1
        else:
            num1_each_digit[i_bit] += 1
ans = 0
for i in range(maxA_len):
    ans += (num0_each_digit[i] * num1_each_digit[i] * (2 ** (maxA_len - i - 1))) % MOD

print(ans % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)

maxA_len = len(bin(maxA)[2:])
num0_each_digit = [0 for _ in range(maxA_len)]
num1_each_digit = [0 for _ in range(maxA_len)]

for i in range(N):
    for i_bit, bit in enumerate(bin(A[i])[2:].zfill(maxA_len)):
        if bit == '0':
            num0_each_digit[i_bit] += 1
            num0_each_digit[i_bit] %= MOD
        else:
            num1_each_digit[i_bit] += 1
            num1_each_digit[i_bit] %= MOD
ans = 0
for i in range(maxA_len):
    factor = (2 ** (maxA_len - i - 1)) % MOD
    ans += (num0_each_digit[i] * num1_each_digit[i] * factor) % MOD

print(ans % MOD)
### BUGGY CODE ###

N, K = map(int, input().split())
p_list = list(map(int, input().split()))

loop_time = N - K

l_s = 0
l_e = K
max_score = 0
test_score = 0
# initial process
ans_list = p_list[l_s:l_e]
for j in ans_list:
    max_score += sum(range(1,j+1)) / j
    test_score = max_score
l_s = l_s + 1

for i in range(loop_time):
    # pop process
    pop_e = p_list[l_s-1]
    test_score = test_score - sum(range(1,pop_e+1)) / pop_e
    # push process
    push_e = p_list[l_e]
    test_score = test_score + sum(range(1,push_e+1)) / push_e
    if test_score > max_score:
        max_score = test_score
    l_s = l_s + 1
    l_e = l_e + 1

print(max_score)


### FIXED CODE ###

N, K = map(int, input().split())
p_list = list(map(int, input().split()))

loop_time = N - K

l_s = 0
l_e = K
max_score = 0
test_score = 0
# initial process
ans_list = p_list[l_s:l_e]
for j in ans_list:
    max_score += sum(range(1,j+1)) / j
    test_score = max_score
l_s = l_s + 1

for i in range(loop_time):
    # pop process
    pop_e = p_list[l_s-1]
    test_score = test_score - sum(range(1,pop_e+1)) / pop_e
    # push process
    push_e = p_list[l_e]
    test_score = test_score + sum(range(1,push_e+1)) / push_e
    if test_score > max_score:
        max_score = test_score
    l_s = l_s + 1
    l_e = l_e + 1

print(max_score)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
ans = min(a)
for j in range(min(a)):
	for i in range(n):
		b[i] = a[i]%ans
	if max(b) == 0:
		break
	else:
		ans = max(b)
print(ans)

### FIXED CODE ###

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

#ユーグリッドの互除法で、a,bを与えて、aをbで割ってあまりを計算する
#あまりがないときは、最後に割った数を返す（最大公約数）
#あまりがあるときは、bにあまりを入れて、再び計算する
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)


x = A[0]
for i in A[1:]:
	x = gcd(x,i)
print(x)
### BUGGY CODE ###

import math
MOD = 10**9+7
x, y = map(int, input().split())
if (x+y)%3 != 0 or 3*x < x+y or 3*y < x+y:
    print(0)
    exit()
n = (x+y)//3
x -= n
y -= n
c = math.factorial(n) // math.factorial(x) // math.factorial(y)
print(c%MOD)


### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

MOD = 10**9+7
x, y = map(int, input().split())
if (x+y)%3 != 0 or 3*x < x+y or 3*y < x+y:
    print(0)
    exit()
n = (x+y)//3
x -= n
y -= n
fact = [1, 1]
for i in range(2,n+1):
    fact.append(fact[i-1] * i % MOD)
factX = fact[x]
factY = fact[y]
factN = fact[n]
# print(x,y,n)
# print(factX,factY,factN)

c = factN * modinv(factX, MOD) * modinv(factY, MOD)
c %= MOD
print(c)
### BUGGY CODE ###

def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n, m = map(int, input().split())
    edge = np.array([input().split() for _ in range(m)], dtype=np.int64).T
    a = csr_matrix(([1] * m, (edge - 1)), shape=(n, n))
    s, p = shortest_path(a, return_predecessors=True,
                         indices=0, directed=False, unweighted=True)
    if min(p[1:]) < -1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    def Dijkstra(s, n, edge, inf=float("inf")):
        import heapq
        d = [inf] * n
        used = [False] * n
        d[s] = 0
        used[s] = True
        queue = []
        path = [-9999] * n
        for e in edge[s]:
            heapq.heappush(queue, e + [s])
        while len(queue):
            dist, point, before = heapq.heappop(queue)
            if used[point]:
                continue
            d[point] = dist
            used[point] = True
            path[point] = before
            for nextdist, nextp in edge[point]:
                if not used[nextp]:
                    heapq.heappush(queue, [dist + nextdist, nextp, point])
        return d, path
    n, m = map(int, input().split())
    inf = 10 ** 10
    edge = [[] for _ in range(n)]
    for _ in range(m):
        x, y = [int(x) - 1 for x in input().split()]
        edge[x].append([1, y])
        edge[y].append([1, x])
    l, p = Dijkstra(0, n, edge, inf)
    if min(p[1:]) < -1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()