Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
import sys

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.predecessor(G, 1)

    ans_list = []
    for key, val in sorted(paths.items()):
        if key != 1:
            ans_list.append((key,val[0]))

    print(YES)
    ans_list.sort(key=lambda x: x[0])
    for key, val in ans_list:
        print(val)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    dq = deque([])
    traversed = [False for _ in range(N+1)]
    ans = [None for _ in range(N+1)]

    G = {n : set([]) for n in range(1, N+1)}
    for a, b in zip(A,B):
        G[a].add(b)
        G[b].add(a)

    dq.append(1)
    traversed[1] = True

    while dq:
        s = dq.popleft()

        for node in G[s]:
            if not traversed[node]:
                dq.append(node)
                traversed[node] = True
                

                ans[node] = s

    print(YES)
    for s in ans:
        if s != None:
            print(s)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
  r=t=j=0;d[0]*h
  while w-j:
    i=c=0
    while(h-i):
      d[c]+=s[i][j]>'0'; x=d[c]>k
      if(t<j)&x:r+=1;t=j;d=[0]*h;break
      r+=h*w*x;c+=b>>i&1;i+=1
      else:j+=1
  m+=r+bin(b).count('1'),
print(min(m))

### FIXED CODE ###

h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=0;t=j=w;d=[0]*h
 while j:
  i=c=0;j-=1
  while h-i:
   d[c]+=s[i][j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j=j,j+(t>j);i=h
 m+=r+c,
print(min(m))
N = int(input())
output = 0

for i in range(N+1):
    output += i

print output

### FIXED CODE ###

N = int(input())
output = 0

for i in range(N+1):
    output += i

print(output)
li = list(input())
li.sort()
while True:
    if len(li) == 0:
        print("Yes")
        break
    elif li[0] == li[1]:
        li.pop(0)
        li.pop(0)
    else:
        print("No")
        break


### FIXED CODE ###

li = list(input())
li.sort()
while True:
    if len(li) == 0:
        print("Yes")
        break
    elif not len(li) % 2 == 0:
        print("No")
        break
    elif li[0] == li[1]:
        li.pop(0)
        li.pop(0)
    else:
        print("No")
        break
n, k = map(int, input().split())

n = n % k
print(min(abs(n - k)), n)

### FIXED CODE ###

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

def solve():
    global n, k
    n = n - (k * (n // k))
    pre = n
    while True:
        n = min(n, abs(n-k))
        if n == pre:
            break
        pre = n
    return n

print(solve())
def get_group(str):
    return str.split(':')[0];

def get_member(str):
    return str.split(':')[1].split('.')[0].split(',');

def get_num(group, map, ans):
    for person in map[group]:
        if person in map:
            get_num(person, map, ans);
        else:
            ans[person] = True;

def main():
    while True:
        str = input();
        if len(str) == 0:
            continue;

        n = int(str);
        if n == 0:
            break;

        group = {};
        group.clear();
        name = {};
        name.clear();

        for i in range(0, n):
            str = input();
            name[i] = get_group(str);
            group[name[i]] = get_member(str);

        ans = {};
        ans.clear();
        get_num(name[0], group, ans);
        print(len(ans));

main();

### FIXED CODE ###

def get_num(u, map, vis):
    if u in vis:
        return 0;
    else:
        vis[u] = True;
    ans = 0;
    if u in map:
        for v in map[u]:
            ans += get_num(v, map, vis);
    else:
            ans += 1;
    return ans;
def main():
    while True:
        n = int(input());
        if n == 0:
            break;
        edge = {}; name = {}; vis = {};
        for i in range(0, n):
            str = input();
            u = name[i] = str.split(':')[0];
            group = str.split(':')[1].split('.')[0].split(',');
            for v in group:
                if u in edge:
                    edge[u][v] = True;
                else:
                    edge[u] = {v:True};
        print(get_num(name[0], edge, vis));
main();
import sys


sys.setrecursionlimit(10 ** 6)


def f(n):
    if memo[n] > 0:
        return memo[n]
    memo[n] = f(n - 1) + f(n - 2)
    return memo[n]


N, M, *A = map(int, open(0).read().split())
memo = [1, 1] + [-1] * N
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)


### FIXED CODE ###

import numpy as np


H, W = map(int, input().split())
field = [[c == "." for c in input()] for _ in range(H)]
field = np.array(field, dtype=np.int16)

u = field.copy()
d = field.copy()
l = field.copy()
r = field.copy()

for i in range(1, H):
    u[i] = (u[i - 1] + 1) * u[i]
    d[-i - 1] = (d[-i] + 1) * d[-i - 1]

for j in range(1, W):
    l[:, j] = (l[:, j - 1] + 1) * l[:, j]
    r[:, -j - 1] = (r[:, -j] + 1) * r[:, -j - 1]

print((u + d + l + r - 3).max())
print (x**3)javascript:void(0)

### FIXED CODE ###

x = int(input())
print(x ** 3)
a,b,c = list(map(int,input().split()))

if b-c > 0 and c-a > 0:
    print("Yes")
else if a-b > 0 and b-c > 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

if b-c > 0 and c-a > 0:
    print("Yes")
elif a-c > 0 and c-b > 0:
    print("Yes")
else:
    print("No")
# -*- coding: utf-8 -*-
from heapq import merge
from bisect import bisect
def inpl(): return list(map(int, input().split()))

X, Y, Z, K = inpl()
A = inpl()
B = inpl()
C = sorted(inpl(), reverse=True)

AB = sorted([a+b for a in A for b in B])[-K:]
ans = [-1] * K

for c in C:
    if ans[0] > AB[-1] * c:
        break
    tmp = [ab + c for ab in AB][-K:]
    ans = list(merge(ans, tmp))[-K:]

print(*ans[::-1], sep="\n")


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

X = [0]*6
for i in range(6):
    X[i] = int(input())
a, b, c, d, e, k = X

for l, r in product(X[:5], repeat=2):
    if abs(l-r) > k:
        print(":(")
        break
else:
    print("Yay!")
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n-2):
    if a[i] < a[i+1] < a[i+2] or a[i+2] < a[i+1] < a[i]
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n-2):
    b = sorted([a[i], a[i+1], a[i+2]])
    if b.index(a[i+1]) == 1:
        cnt += 1
print(cnt)
A,B  = map(float, input().split())
print(int(A * B))
N = int(input())
lst = list(map(int, input().split()))
res = 1
if 0 in lst:
    res = 0
for x in lst:
    res *= x
    if res > 10**18:
        res = -1
print(res)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
def main():
    N, M, X = map(int, input().split())

    books = [list(map(int, input().split())) for _ in range(N)]

    min_total_cost = 10**9

    for i in range(2**N):
        total_cost = 0
        learned = [0] * M

        for j in range(N):
            if (i >> j) & 1:
                cost, points = books[j]
                total_cost += cost
                
                learned = [x + y for x, y in zip(learned, points)]

        if min(learned) >= X:
            min_total_cost = min(min_total_cost, total_cost)

    if min_total_cost == 10**9:
        print('-1')
    else:
        print(min_total_cost)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# import numpy as np
# import queue
# import heapq


def main():
    N, M, X = map(int, input().split())

    books = [list(map(int, input().split())) for _ in range(N)]

    min_total_cost = 10**9
    for i in range(2**N):
        total_cost = 0
        learned = [0] * M

        for j in range(N):
            if (i >> j) & 1:
                C, *As = books[j]
                total_cost += C

                for ids, a in enumerate(As):
                    learned[ids] += a

        if min(learned) >= X:
            min_total_cost = min(min_total_cost, total_cost)

    if min_total_cost == 10**9:
        print('-1')
    else:
        print(min_total_cost)


if __name__ == "__main__":
    main()
a, b, n = [int(x) for x in input().split()]
x = min(b - 1, n)
answer = floor(a * x / b) - a * floor(x / b)
print(answer)

### FIXED CODE ###

from math import floor
a, b, n = [int(x) for x in input().split()]
x = min(b - 1, n)
answer = floor(a * x / b) - a * floor(x / b)
print(answer)
import sys
sys.stdin = open('input.txt', 'r', encoding='utf-8')

s = input()
t = input()

if t == s + t[-1]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
t = input()

if t == s + t[-1]:
    print('Yes')
else:
    print('No')
# -*- coding: utf-8 -*-
a, b = map(int, input().split())
x = (a + b) / 2
if x > 0:
    return x + 1
else:
    return x


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

a, b = map(int, input().split())
x = (a + b) / 2
print(math.ceil(x))
print(1100 - int(input())

### FIXED CODE ###

print(1110 - int(input()))
n = int(input())
a = list(map(int, input().split()))
na = [0]*n
for i in range(n):
    na[i] = a[i]-(i+1)
mid = sum(na)//n
mid1 = mid+1
ans = 0
ans1 = 0
for i in range(n):
    ans += abs(na[i]-mid)
    ans1 += abs(na[i]+mid1)
print(min(ans, ans1))

### FIXED CODE ###

n = int(input())
if n % 2 == 0:
    print(n)
else:
    print(2*n)
s=input()
c=0
for k in range(4,len(s)+1):
  for i in range(0,s+1-k):
    if int(s[i:i+k])%2019==0:
      c+=1
print(c)
  

### FIXED CODE ###

s=input()
r=set()
last=0
power=1
d={0:0}
total=0
rem=0
for i in range(len(s)-1,-1,-1):#handling of 0's as n and rem
    n=int(s[i])*power+rem
    power*=10
    power=power%2019
    rem=n%2019
    if rem in d.keys():
        d[rem]+=1
    else:
        d[rem]=1
    total+=d[rem]-1
print(total+d[0])
# -*- coding: utf-8 -*-
S = input()
n = len(S)
L = list(map(int, list(S)))
D = []
res = 0
for k in range(n-1):
    if L[k] != L[k+1]:
        D.append(max(k+1, n-k-1))

print(min(D))

### FIXED CODE ###

# -*- coding: utf-8 -*-
S = input()
n = len(S)
L = list(map(int, list(S)))
D = []
res = 0
for k in range(n-1):
    if L[k] != L[k+1]:
        D.append(max(k+1, n-k-1))

if len(D):
    print(min(D))
else:
    print(n)
import sys

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    for i_node in TREE[parent]:
        if i_node[0] == child:
            TO_K[child] = TO_K[parent] + i_node[1]

    for i_gch in TREE[child]:
        if i_gch[0] == parent:
            TO_K[child] = TO_K[parent] + i_gch[1]
        else:
            dfs(i_gch[0], child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    dfs(k, 0)

    for x, y in xy:
        print(TO_K[x]+TO_K[y])
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

TO_K = []
TREE = []

def dfs(parent, distance):
    for i_node in TREE[parent]:
        child, dd = i_node
        if TO_K[child] != -1:
            continue

        next_dt = distance + dd
        TO_K[child] = next_dt
        dfs(child, next_dt)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [-1]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    TO_K[k] = 0
    dfs(k, 0)

    for x, y in xy:
        print(TO_K[x]+TO_K[y])
    return


if __name__ == "__main__":
    main()
    sys.exit(0)
n, t = map(int, input())
ct = [map(int(input())) for _ in range(n)]

li = []
for i in range(n):
  if ct[i][1] < t:
    li.append(ct[i])
  else:
    continue

if count(li) > 0:
  print(min(li[:][0]))
else:
  print("TLE")

### FIXED CODE ###

n, t = map(int, input().split())
ct = [list(map(int,input().split())) for _ in range(n)]

li = []
for i in range(n):
  if ct[i][1] <= t:
    li.append(ct[i])
  else:
    continue

if len(li) > 0:
  li2 = []
  for i in range(len(li)):
    li2.append(li[i][0])
  print(min(li2))
else:
  print("TLE")
from statistics import mean, median, variance, stdev

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

A2 = [a-(idx+1) for idx, a in enumerate(A)]
# print(A2, sum(A2), median(A2))

center = median(A2)

ans = 0
for a in A2:
    ans += abs(a-center)
print(int(ans))

### FIXED CODE ###

from statistics import mean, median, variance, stdev

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

A2 = [a-(idx+1) for idx, a in enumerate(A)]
# print(A2, sum(A2), median(A2))

center = median(A2)

ans = 0
for a in A2:
    ans += abs(a-center)
print(int(ans))
a,b=map(int,input().split())
x= (a=="H")
y=(b=="H")
if :x and y or not x and not y
  print("H")
else:
  print("D")

### FIXED CODE ###

a,b=input().split()
x= (a=="H")
y=(b=="H")
if x and y or not x and not y:
  print("H")
else:
  print("D")
N, M, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
timeA, timeB = 0, 0
numA, numB = 0, 0
for i in range(N):
    if timeA + A[i] <= K:
        numA += 1
        timeA += A[i]
    else:
        break
for i in range(M):
    if timeB + B[i] <= K - timeA:
        numB += 1
        timeB += B[i]
    else:
        break
ans = numA + numB
t = numA
j = numB
for i in reversed(range(numA)):
    t -= 1
    timeA -= A[i]
    while j < M:
        if timeB + B[j] <= K - timeA:
            numB += 1
            timeB += B[i]
        else:
            break
    ans = max(ans, t + numB)
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
timeA, timeB = 0, 0
numA, numB = 0, 0
for i in range(N):
    if timeA + A[i] <= K:
        numA += 1
        timeA += A[i]
    else:
        break
for i in range(M):
    if timeB + B[i] <= K - timeA:
        numB += 1
        timeB += B[i]
    else:
        break
ans = numA + numB
t = numA
for i in reversed(range(numA)):
    t -= 1
    timeA -= A[i]
    while numB < M:
        if timeB + B[numB] <= K - timeA:
            timeB += B[numB]
            numB += 1
        else:
            break
    ans = max(ans, t + numB)
print(ans)
N, K = map(int, input().split())

for i in range(1, N+2):
    saisyo += i-1
    saidai += N-i+1
    if i >= K:
        ans += (saidai - saisyo + 1)
    
print(ans%(10**9+7))

### FIXED CODE ###

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

ans, saidai, saisyo = 0, 0, 0
for i in range(1, N+2):
    saisyo += i-1
    saidai += N-i+1
    if i >= K:
        ans += (saidai - saisyo + 1)
    
print(ans%(10**9+7))
import math
from functools import reduce

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

#最小公倍数-1
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

MaxKoubai = lcm_list(a)
m = MaxKoubai - 1
result = 0

for i in range(N):
    result += m % a[i]
    
print(result)

### FIXED CODE ###

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

answer = A[0]
Sum = 0

def gcd(A,B):
    if(B == 0):
        return A
    else:
        return gcd(B, A%B)

#最小公倍数-1がfに入る数なはず
for i in range(1, N):
    answer = answer * A[i] // gcd(answer, A[i])
    
for i in range(N):
    Sum += (answer-1) % A[i]

print(Sum)
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
total = 0
div = c1[0]+c2[1]+c3[2]
for (x,y,z) in zip(c1,c2,c3):
    total = total + x + y + z

print ('Yes' if total / div == 3 else 'No')

### FIXED CODE ###

c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
total = 0
div = c1[0]+c2[1]+c3[2]
for (x,y,z) in zip(c1,c2,c3):
    total = total + x + y + z

print ('Yes' if total / 3 == div else 'No')
import sys

n = int(input()) 
s = list(input()) 
k = int(input()) 

word = s[k]
for i in s:
    if i != word:
        sys.stdout.write('*')
    else:
        sys.stdout.write(i)

### FIXED CODE ###

import sys

n = int(input()) 
s = list(input()) 
k = int(input()) 

word = s[k-1]
for i in s:
    if i != word:
        sys.stdout.write('*')
    else:
        sys.stdout.write(i)
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    if N % 2 == 1:
        print(0)
    else:
        N //= 2
        count = 0
        while N > 1:
            N //= 5
            count += N
            
    print(count)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    if N % 2 == 1:
        print(0)
    else:
        N //= 2
        count = 0
        while N > 1:
            N //= 5
            count += N
        print(count)
    
if __name__ == "__main__":
    main()
from collections import Counter
input()
c = Counter([min(int(i)//400,8) for i in input().split()])
lt3200 = [bool(c[i]) for i in range(8)].count(True)
print(max(1, lt3200), lt3200+c[8])

### FIXED CODE ###

print('YES' if int(input().replace(' ','')[1:])%4==0 else 'NO')
stack = []
n = int(raw_input())
for i in range(n):
    stack.append([])

while True:
    s = raw_input()
    if s.find("push") != -1:
        stack[int(s[5])-1].append(s[7])
    elif s.find("pop") != -1:
        print stack[int(s[4])-1][len(stack[int(s[4])-1])-1]
        stack[int(s[4])-1].pop()
    elif s.find("move") != -1:
        stack[int(s[7])-1].append(stack[int(s[5])-1][len(stack[int(s[5])-1])-1])
        stack[int(s[5])-1].pop()
    else :
        break

### FIXED CODE ###

stack = []
n = int(raw_input())
for i in range(n):
    stack.append([])

while True:
    s = raw_input().split(" ")
    if s[0] == "push":
        stack[int(s[1])-1].append(s[2])
    elif s[0] == "pop":
        print stack[int(s[1])-1][len(stack[int(s[1])-1])-1]
        stack[int(s[1])-1].pop()
    elif s[0] == "move":
        stack[int(s[2])-1].append(stack[int(s[1])-1][len(stack[int(s[1])-1])-1])
        stack[int(s[1])-1].pop()
    else :
        break
class UnionFind:
    def __init__(self, length):
        self.par = [_ for _ in range(length)]
        self.size_dict  = dict([(i,1) for i in range(length)])

    def root(self,x):
        if (self.par[x] == x):
             return x
        else:
            #change connection 
            self.par[x] =self.root(self.par[x])
            return self.par[x]
    
    def unite(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if (root_x==root_y):
            pass
        else:
            self.par[root_x] = root_y
            self.size_dict[root_y] += self.size_dict[root_x]
            self.size_dict[root_x] = -1
        
    def same(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        return root_x == root_y 
    
    def size(self,x):
        root_x = self.root(x)
        return self.size_dict[root_x]

"""
uf = UnionFind(5)
uf.unite(3,4)
uf.unite(1,2)
uf.unite(1,4)
print(uf.size_dict)
"""


N,M = [ int(i) for i in input().split(" ")]
edges = [ tuple([ int(num)-1 for num in  input().split(" ")]) for _ in range(M) ]
score= N*(N-1)//2
outputs = [score]
uf = UnionFind(N)
for edge in edges[::-1]:
    if not uf.same(*edge):
        score -= uf.size(edge[0]) * uf.size(edge[1])
        uf.unite(*edge)
    outputs.append(score)
for i in range(M):
    print(int(outputs[M-i-1]))



### FIXED CODE ###

class UnionFind:
    def __init__(self, length):
        self.par = [-1 for _ in range(length)]
        self.rank = [0 for _ in range(length)]
 
    def root(self,x):
        if (self.par[x] < 0 ):
             return x
        else:
            #change connection
            root = self.root(self.par[x])
            self.par[x] = root
            return root
    
    def unite(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if (root_x==root_y):
            return 
        else:
            if self.rank[root_x] < self.rank[root_y]:
                self.par[root_y] += self.par[root_x]
                self.par[root_x] = root_y

            else:
                self.par[root_x] += self.par[root_y]
                self.par[root_y] = root_x
                if self.rank[root_x] == self.rank[root_y]:
                    self.rank[root_x]+=1
        
    def same(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        return root_x == root_y 
    
    def size(self,x):
        return -self.par[self.root(x)]

"""
uf = UnionFind(5)
uf.unite(3,4)
uf.unite(1,2)

uf.unite(1,4)
print(uf.size_dict)
"""
def solve(edges,N,M):
 
    score= N*(N-1)//2
    outputs = [score]
    uf = UnionFind(N)
    for edge in edges[::-1]:
        if not uf.same(*edge):
            score -= uf.size(edge[0]) * uf.size(edge[1])
            uf.unite(*edge)
        outputs.append(score)
    for i in range(M):
        print(int(outputs[M-i-1]))

def get_input():
    N,M = map(int, input().split())
    edges = [tuple(map(lambda x:  int(x)-1, input().split())) for _ in range(M)]
    return N,M,edges

N,M,edges = get_input()
# = 10**6
#M=10**5
#import numpy as np
#edges = [(np.random.randint(N),np.random.randint(N)) for i in range(M)]
solve(edges,N,M)
print(“aA”[input().isupper()])

### FIXED CODE ###

print("aA"[input().isupper()])