Harryxun/stf_run huggingface dataset:
def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)


N, Q = map(int, input().split())
to = [[] for _ in range(20005)]
ans = [0 for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0)
print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
N = int(input())
T = list(map(int,input().split()))
M = int(input())
P = [0]*M
X = [0]*M
for i in range(M):
	P[i],X[i] = map(int,input().split())

for i in range(M):         
	print(sum(T)-T[i]+X[i]) 

### FIXED CODE ###

N = int(input())
T = list(map(int,input().split()))
M = int(input())
P = [0]*M
X = [0]*M
for i in range(M):
	P[i],X[i] = map(int,input().split())

for i in range(M):         
	print(sum(T)-T[P[i]-1]+X[i])
import numpy as np
import itertools
N, M, X = map(int, input().split())
kumi = []
pat = list(range(N))
for _ in range(N):
    kumi.append(list(map(int, input().split())))
ans0 = 10 ** 5 * 12
ans = 10 ** 5 * 12
#print(kumi)
test = []
for i in range(N):
    for i2 in itertools.combinations(kumi,i+1):
        arr_i2 = np.array(i2)
        arr_i2_sum = arr_i2.sum(axis = 0)
        #print(arr_i2_sum[1:] >= X)
        if np.all(arr_i2_sum[1:] >= X):
            if ans > arr_i2_sum[0]:
                ans = arr_i2_sum[0]
if ans == ans0:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import itertools
N, M, X = map(int, input().split())
kumi = []
pat = list(range(N))
for _ in range(N):
    kumi.append(list(map(int, input().split())))
ans = 10 ** 5 * 12
kai = False
test = []
for i in range(N):
    for i2 in itertools.combinations(kumi,i+1):
        arr_i2 = np.array(i2)
        arr_i2_sum = arr_i2.sum(axis = 0)
        if np.all(arr_i2_sum[1:] >= X):
            if ans >= arr_i2_sum[0]:
                ans = arr_i2_sum[0]
                kai = True
if kai:
    print(ans)
else:
    print(-1)
import itertools
n,m,q=map(int,input().split())
lis=[i for i  in range(1,m+1)]
lis=list(itertools.combinations(lis,n))
box=[0 for j in range(len(lis))]
que=[list(map(int,input().split())) for k in range(q)]
for i in range(q):
    for j in range(len(lis)):
        if lis[j][que[i][1]-1]-lis[j][que[i][0]-1]==que[i][2]:
            box[j]+=que[i][3] 
print(max(box))


### FIXED CODE ###

import itertools
n,m,q=map(int,input().split())
lis=[i for i  in range(1,m+1)]
lis=list(itertools.combinations_with_replacement(lis,n))
box=[0 for j in range(len(lis))]
for i in range(q):
    que=list(map(int,input().split()))
    for j in range(len(lis)):
        if lis[j][que[1]-1]-lis[j][que[0]-1]==que[2]:
            box[j]+=que[3] 
print(max(box))
(n, m) = [int(i) for i in input().split()]
for i in range(1,n-1):
    for j in range(i+1,n):
        for k in range(j+1,n+1):
            if i+j+k==x:ans+=1
print ans

### FIXED CODE ###

while True:
    (n, x) = [int(i) for i in input().split()]
    if n == x == 0: break
    ans = 0
    for i in range(1,n-1):
        for j in range(i+1,n):
            c=x-i-j
            if c>j and c<=n:
                ans+=1
    print (ans)
from collections import deque
import sys
sys.setrecursionlimit(100000)
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(1, N):
    tmpa, tmpb, tmpc = map(int, input().split())
    graph[tmpa].append((tmpb, tmpc))
    graph[tmpb].append((tmpa, tmpc))

Q, K = map(int, input().split())
question = [[] for _ in range(Q+1)]
for i in range(1, Q+1):
    question[i] = list(map(int, input().split()))

#print(graph)
#print(question)
seen = [False] * (N+1)
dist = [0] * (N+1)
#Kからdfs
def dfs(here, seen, kyori):
    seen[here] = True
    dist[here] = kyori
    #print(f"here:{here} kyori:{kyori}")
    for node in graph[here]:
        nextkyori = kyori
        if not seen[node[0]]:
            nextkyori += node[1]
            dfs(node[0], seen, nextkyori)

dfs(K, seen, 0)
for quest in question[1:]:
    print(dist[quest[0]] + dist[quest[1]])


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(1000000)
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(1, N):
    tmpa, tmpb, tmpc = map(int, input().split())
    graph[tmpa].append((tmpb, tmpc))
    graph[tmpb].append((tmpa, tmpc))

Q, K = map(int, input().split())
question = [[] for _ in range(Q+1)]
for i in range(1, Q+1):
    question[i] = list(map(int, input().split()))

#print(graph)
#print(question)
seen = [False] * (N+1)
dist = [0] * (N+1)
#Kからdfs
def dfs(here, seen, kyori):
    seen[here] = True
    dist[here] = kyori
    #print(f"here:{here} kyori:{kyori}")
    for node in graph[here]:
        nextkyori = kyori
        if not seen[node[0]]:
            nextkyori += node[1]
            dfs(node[0], seen, nextkyori)

dfs(K, seen, 0)
for quest in question[1:]:
    print(dist[quest[0]] + dist[quest[1]])
# AtCorder

s = input()

a = "ACGT"
v = 0
ans = []

for i in s:
    if i in a:
        v += 1
    else:
        if v != 1:
            ans.append(v)
        v = 0

print(max(ans))

### FIXED CODE ###

# AtCorder

s = input()

a = "ACGT"
v = 0
ans = 0

for i in s:
    if i in a:
        v += 1
        ans = max(ans, v)
    else:
        v = 0

print(ans)
n, m = map(int, input().split())
broken = [0] * n
dp = [0] * (n+1)
in_memo = [0] * (n+1)
for i in range(m):
    broken[int(input())] = 1

def solve(i):
    if(not in_memo[i]):
        if i == n:
            dp[i] = 1
        elif i == n-1:
            dp[i] = 0 if broken[i] else 1
        else:
            dp[i] = 0 if broken[i] else (solve(i+1)+solve(i+2)) % 1000000007
        in_memo[i] = 1
    return dp[i]

print(solve(0))

### FIXED CODE ###

n, m = map(int, input().split())
ok = [1] * n
for i in range(m):
    x = int(input())
    ok[x-1] = 0
mod = 1000000007
dp = [0] * (n+2)
dp[1] = 1
for i in range(n):
    dp[i+2] = (dp[i+1] + dp[i])%mod if ok[i] else 0

print(dp[n+1])
import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: 
        return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1

        
    else:
        calc=K-2
        num-=1
    """
    loop=range(calc,calc-(num-diff),-1)
    for i in loop:
        seki*=i%1000000007
    """
    seki=(math.factorial(calc)//math.factorial(calc-num))%mod
    #"""
    #if calc-num>=0:
        #fac=math.factorial(calc-(num-diff))%mod
        #seki*=((math.factorial(calc)%mod)*power_func(fac,mod-2,mod))%mod
        #seki=(math.factorial(calc)//math.factorial(calc-num))%mod
    #else:
    #    return 0
    #"""
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


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

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)
import math
N = input()
answers = []
for val in range(1,N+1):
	x = map(float,raw_input().split(' '))
	d = math.fabs(math.sqrt((x[0]-x[3])**2 - (x[1]-x[4])**2))
	s = x[2]+x[5]
	r = math.fabs(x[2]-x[5])
	if r >= d:
		if x[2] > x[5]:
			answers.append(2)
		else:
			answers.append(-2)
	elif s < d:
		answers.append(0)
	else:
		answers.append(1)
for val in answers:
	print val

### FIXED CODE ###

import math
N = input()
answers = []
for val in range(1,N+1):
	x = map(float,raw_input().split(' '))
	d = (x[0]-x[3])**2 + (x[1]-x[4])**2
	d = math.sqrt(d)
	d = math.fabs(d)
	s = x[2]+x[5]
	r = math.fabs(x[2]-x[5])
	if d > s:
		answers.append(0)
	elif d == s:
		answers.append(1)
	elif d < s:
		if d < r:
			if x[2] > x[5]:
				answers.append(2)
			else:
				answers.append(-2)
		elif d >= r:
			answers.append(1)
for val in answers:
	print val
# ABC 093: B – Small and Large Integers
a, b, k = [int(s) for s in input().split()]
nums = list(range(a, b + 1))
result = []

if k > len(nums):
    result = nums
else:
    result = [nums[i] for i in set(list(range(0, k)) + list(range(len(nums) - k, len(nums))))]

for num in result:
    print(num)

### FIXED CODE ###

# ABC 093: B – Small and Large Integers
a, b, k = [int(s) for s in input().split()]

if k >= b - a + 1:
    for c in list(range(a, b + 1)):
        print(c)
else:
    s = set(list(range(a, a + k)) + list(range(b - k + 1, b + 1)))
    list_s = list(s)
    list_s.sort()

    for c in list_s:
        print(c)
H,W = map(int,input().split())
move_x = [1,-1,0,0]
move_y = [0,0,1,-1]
Field = [[c for c in input()] for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]
queue = []
black = 0
for i in range(H):
    for j in range(W):
        if Field[i][j] == '#':
            black += 1
dist = [[0 for _ in range(W)] for _ in range(H)]
res = -1 
def bfs(start_x,start_y,Field,seen,queue,dist):
    global res
    seen[start_x][start_y] = True
    for i in range(0,4):
        x = start_x + move_x[i]
        y = start_y + move_y[i]
        if x < 0 or y < 0 or x >= H or y >= W:
            continue #out of range
        if Field[x][y] == '#':
            continue #we don't visit black square.
        if seen[x][y]:
            continue #already visited
        if Field[x][y] in queue:
            continue #already in queue.
        if x == (H-1) and y == (W-1):
            dist[x][y] = dist[start_x][start_y] + 1
            res = H*W - dist[x][y] - black #H*W - counting(seen) - black 
        queue.append((x,y))
        dist[x][y] = dist[start_x][start_y] + 1
    for element in queue:
        x,y = element
        if seen[x][y]:
            continue
        seen[x][y] = True
        queue.remove(element)
        bfs(x,y,Field,seen,queue,dist)    
bfs(0,0,Field,seen,queue,dist)
print(res-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
H,W = map(int,input().split())
move_x = [1,-1,0,0]
move_y = [0,0,1,-1]
Field = [[c for c in input()] for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]
queue = []
black = 0
for i in range(H):
    for j in range(W):
        if Field[i][j] == '#':
            black += 1
dist = [[0 for _ in range(W)] for _ in range(H)]
res = -1 
def bfs(start_x,start_y,Field,seen,queue,dist):
    global res
    seen[start_x][start_y] = True
    for i in range(0,4):
        x = start_x + move_x[i]
        y = start_y + move_y[i]
        if x < 0 or y < 0 or x >= H or y >= W:
            continue #out of range
        if Field[x][y] == '#':
            continue #we don't visit black square.
        if seen[x][y]:
            continue #already visited
        if Field[x][y] in queue:
            continue #already in queue.
        dist[x][y] = dist[start_x][start_y] + 1
        if x == (H-1) and y == (W-1):
            res = H*W - dist[x][y] - black #H*W - counting(seen) - black 
        queue.append((x,y))
    for element in queue:
        x,y = element
        if seen[x][y]:
            continue
        seen[x][y] = True
        queue.remove(element)
        bfs(x,y,Field,seen,queue,dist)    
bfs(0,0,Field,seen,queue,dist)
if res != -1:
	print(res-1)
else:
  print(-1)
n = int(input())
a_list = list(map(int, input().split()))

b = sum(a_list)//n

def temp(a):
  return (a-b)^2
def temp2(a):
  return (a-b-1)^2

ans1 = sum(list(map(temp, a)))
ans2 = sum(list(map(temp2, a)))
#ans1 = sum([(a-b)^2 for a in a_list])
#ans2 = sum([(a-b-1)^2 for a in a_list])

print(min(ans1,ans2))


### FIXED CODE ###

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

b = sum(a_list) // n
ans1 = sum([(a-b)**2 for a in a_list])

b += 1
ans2 = sum([(a-b)**2 for a in a_list])

print(min(ans1,ans2))
n=int(input())
node=[0 for i in range(n)]
chil=[[] for i in range(n)]
change=[True for i in range(n)]
def renew(i):
  if chil[i]==[]:
    node[i]=abs(node[i]-1)
  else:
    for j in chil[i]:
      if change[j]:
        node[j]=abs(node[j]-1)
        change[j]=False
        renew(j)
  return
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  t=w%2
  if t:
    if node[u]==node[v]:
      renew(v)
    else:
      pass
  else:
    if node[u]!=node[v]:
      renew(v)
    else:
      pass
  chil[u].append(v)
  chil[v].append(u)
  change=[True for i in range(n)]
for i in node:
  print(i)

### FIXED CODE ###

n=int(input())
node=[-1 for i in range(n)]
g=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])
queue=[0]
node[0]=0
while len(queue)>0:
  t=queue.pop()
  for v,w in g[t]:
    if node[v]>-1:
      continue
    node[v]=node[t]^w
    queue.append(v)
for i in range(n):
  print(node[i])
# Longest path
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1)
dp = [-1 for _ in range(N)]

def rec(c):
    if dp[c] != -1:
        return dp[c]
    res = 0
    for i in graph[c]:
        res = max(res, rec(i) + 1)
    dp[c] = res
    return res

for i in range(N):
    rec(i)
print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)
a,b=int(input().split())
op = input().split()
if(op == "+"):
    print(a+b)
elif(op == "-"):
    print(a-b)


### FIXED CODE ###

a,op,b=input().split()
if(op == "+"):
    print(int(a)+int(b))
elif(op == "-"):
    print(int(a)-int(b))
N, K = map(int, input().split())
a = []
for i in range(K):
  di = int(input())
  for j in range(di):
    a.append(map(int, input().split())

a = set(a)
print(N - len(a))             
    

### FIXED CODE ###

N, K = map(int, input().split())
a = []
for i in range(K):
  di = int(input())
  a += list(map(int, input().split()))

a = set(a)
print(N - len(a))
def segfunc(x, y): return max(x, y)

def init(tmpn):
    global noden
    n = 1
    while tmpn > n:
        n *= 2
    noden = n

def update(i, x):
    i += noden-1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2+1], node[i*2+2])

def query(l, r):
    L = l + noden
    R = r + noden
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(N-1).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * MAX_N - 1)
noden = 0
INF = 0
init(N)
ma = max(a)
ans = 0
for i in a:
    tmp = query(max(i - K, 0), min(ma, i + K) + 1)
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)

### FIXED CODE ###

def segfunc(x, y): return max(x, y)

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))
S=input()
if(len(S)%2==0):
  for in in range(S//2):
    if(S[2*i]!="h" or S[2*i+1]!="i"):
      print("No")
      break
  else:
    print("Yes")
else:
  print("No")

### FIXED CODE ###

S=input()
if(len(S)%2==0):
  for i in range(len(S)//2):
    if(S[2*i]!="h" or S[2*i+1]!="i"):
      print("No")
      break
  else:
    print("Yes")
else:
  print("No")
while True:
	W = list(input())
	if W[0] == '-':
		break
	times = int(input())
	for i in range(times):
		h = int(input())
		W = W[h:]+W[0:h]
	print(X)

### FIXED CODE ###

while True:
	W = list(input())
	if W[0] == '-':
		break
	times = int(input())
	for i in range(times):
		h = int(input())
		W = W[h:]+W[0:h]
	print(*W, sep='')
x=int(input())
y=int(input())
print(x*y)

### FIXED CODE ###

x,y = map(int,input().split())
print(x*y,(x+y)*2)
import math

N/x=math.ceil(a)
a*T=aa

print(aa)

### FIXED CODE ###

n,x,t = input().split()

b = -(-int(n)//int(x))
a = b*int(t)

print(a)
def gcd(a, b):
    if a > b:
        a, b = b, a
    while b > 0:
        a, b = b, a % b
    return a


def allgcd(d):
    if len(d) == 1:
        return d
    ret_gcd = d[0]
    for i in d:
        ret_gcd = gcd(ret_gcd, i)
    return ret_gcd


def maxNumVisitCity(N, X, x):
    if len(x) == 1:
        return abs(x[0] - X)

    d = []
    for i in x:
        d.append(abs(i - X))
    return allgcd(d)


def main():
    N, X = map(int, input().split())
    x = map(int, input().split())
    print(maxNumVisitCity(N, X, x))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def gcd(a, b):
    if a > b:
        a, b = b, a
    while b > 0:
        a, b = b, a % b
    return a


def allgcd(d):
    if len(d) == 1:
        return d
    ret_gcd = d[0]
    for i in d:
        ret_gcd = gcd(ret_gcd, i)
    return ret_gcd


def maxNumVisitCity(N, X, x):
    if len(x) == 1:
        return abs(x[0] - X)

    d = []
    for i in x:
        d.append(abs(i - X))
    return allgcd(d)


def main():
    N, X = map(int, input().split())
    x = list(map(int, input().split()))
    print(maxNumVisitCity(N, X, x))


if __name__ == '__main__':
    main()
import sys
a, b = map(int, sys.stdin.readline().rstrip())
c = a * b
if c % 2 == 0: print 'Even'
else:          print 'Odd'

### FIXED CODE ###

import sys
a, b = map(int, sys.stdin.readline().rstrip().split())
c = a * b
if c % 2 == 0: print 'Even'
else:          print 'Odd'
k,x = int(input().split())

if 500 * k > x :
    print("Yes")
else :
    print("No")

### FIXED CODE ###

k,x = map(int,input().split())

if k * 500 >= x:
    print("Yes")
else:
    print("No")
import math
def c(x,y):
  if x < y or y < 0:
    return 0
  elif x == 0 or y == 0:
    return 1
  else:
    s = math.factorial(n)
    t = math.factorial(n-k)
    u = math.factorial(k)
    return s//(t*u)


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

for i in range(1,k+1):
  sol = c(n-k+1,i)*c(k-1,i-1)
  m = 10**9 +7
  ans = sol%m
  print(ans)

### FIXED CODE ###

s = str(input())

if (s[0] == s[1]) and (s[2] == s[3]) and (s[1] == s[2]):
  print('No')
elif (s[0] == s[1]) and (s[2] == s[3]):
  print('Yes')
elif (s[0] == s[2]) and (s[1] == s[3]):
  print('Yes')
elif (s[0] == s[3]) and (s[2] == s[1]):
  print('Yes')
else:
  print('No')
n, m = [int(i) for i in input().split(" ")]
e = []
par = [i for i in range(0, n + 1)]
count = [1] * (n + 1)
unu = [0] * n

for i in range(0, m):
    e.append([int(j) for j in input().split(" ")])

def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

def unite(x, y, e):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        unu[e] = count[x] * count[y]
        count[y] += count[x]
        par[x] = y

for i in reversed(range(0, m)):
    unite(e[i][0], e[i][1], i)

s = 0
for i in range(0, m):
    s += unu[i]
    print(s)

### FIXED CODE ###

import sys

n, m = [int(i) for i in input().split(" ")]
e = []
par = [i for i in range(0, n + 1)]
count = [1] * (n + 1)
unu = [0] * m

sys.setrecursionlimit(10**6)

for i in range(0, m):
    e.append([int(j) for j in input().split(" ")])

def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

def unite(x, y, e):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        unu[e] = count[x] * count[y]
        count[y] += count[x]
        par[x] = y

for i in reversed(range(0, m)):
    unite(e[i][0], e[i][1], i)

s = 0
for i in range(0, m):
    s += unu[i]
    print(s)