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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
N, M, Q = LI()

abcd = []
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans

def n2kdigit(n, k):
    bi=''
    before = 1
    while n!=0:
        if before <= (n % k):
            # print(n)
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi[::-1]) < N:
        return None
    return bi
ans = 0
for i in range((M + 1) ** (N)):
    A = n2kdigit(i, M + 1)
    # print(A)
    if A is not None:
        ans = max(ans, cal_ans([int(i) for i in A]))
print(ans)

### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import itertools
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
N, M, Q = LI()

abcd = []

all = 0
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
    all += d

abcd = sorted(abcd, key= lambda x:x[3], reverse= True)
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans

def n2kdigit(n, k):
    bi=''
    before = 1
    while n!=0:
        if before <= (n % k):
            # print(n)
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi) < N:
        return None
    return bi
ans = 0

for i in itertools.combinations_with_replacement(range(1, M+1), N):
    # print(i)
    ans = max(ans, cal_ans(i))
print(ans)
### BUGGY CODE ###

import sys
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [[0,0] for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = [h-1,w-1]
h_max = max(h_ls)
h_max_args = []
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args.append(i)

w_max = max(w_ls)
w_max_args = []
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args.append(i)

for h in h_max_args:
    for w in w_max_args:
        if not [h,w] in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)

### FIXED CODE ###

import sys
from collections import Counter
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [(0,0) for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = (h-1,w-1)

h_max = max(h_ls)
h_counter = Counter(h_ls)
# Couter使ってみる
h_max_args = [0]*h_counter[h_max]
next_ind = 0
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args[next_ind] = i
        next_ind += 1

w_max = max(w_ls)
w_counter = Counter(w_ls)
w_max_args = [0]*w_counter[w_max]
next_ind = 0
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args[next_ind] = i
        next_ind += 1

bombers = set(bombers)
for h in h_max_args:
    for w in w_max_args:
        if not (h,w) in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)
### BUGGY CODE ###

import itertools


N = int(input())
S = input()

ptn = [i for i in range(N)]

cnt = 0
for i in range(1, N+1):
    c = list(itertools.combinations(ptn, i))
    for v in c:
        tmp = ''
        for _ in v:
            tmp += S[_]
        if (len(tmp) == len(set(tmp))):
            cnt += 1

print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

M = 10**9 + 7
cnt = [0] * 26

for i in range(N):
    cnt[ord(S[i]) - ord('a')] += 1

ans = 1
for i in range(26):
    ans *= (cnt[i] + 1)
    ans %= M

print(ans - 1)
### BUGGY CODE ###

from collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=input().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.popleft()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.append(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)


### FIXED CODE ###

from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    numbers[u].append((v,w%2))
    numbers[v].append((u,w%2))
inf=pow(10,9)
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    for v,w in numbers[n]:
        if visited_point[v]==inf:
            stack.appendleft(v)
            if w%2==0:
                visited_point[v]=visited_point[n]
            else:
                visited_point[v]=visited_point[n]^1
for a in visited_point:
    print(a)
### BUGGY CODE ###

N, M = map(int, input().split())
ans = 1
if N == 1:
    print(M)
elif M % 2 == 0:
    for i in range(2, M//N+1):
        if M % i == 0:
            ans = i
    print(ans)
else:
    for i in range(3, M//N+1, 2):
        if M % i == 0:
            ans = i
    print(ans)


### FIXED CODE ###

import math
N, M = map(int, input().split())
tmp = [1]
if N == 1:
    print(M)
else:
    for i in range(2, int(math.ceil(M**0.5))):
        if M % i == 0:
            tmp.append(i)
            tmp.append(int(M/i))
    ans = 1
    for x in tmp:
        if M / x >= N:
            ans = max(ans, x)
    print(ans)
### BUGGY CODE ###

s=int(input())

#0<= x,y <=10**9
#s/2

for i in range(int(s**0.5)):
    ss=int(s**0.5)-i
    if s%ss==0:
        print(0,0,ss,0,0,s//ss)
        exit()



### FIXED CODE ###

import sys
input=sys.stdin.readline

s=int(input())

#0<= x,y <=10**9
#s/2

if s<=10**9:
    print(0,0,1,0,0,s)
    exit()

y=(-1*s//(10**9))*(-1)
x=10**9*y-s

print(0,0,10**9,1,x,y)
### BUGGY CODE ###

from math import floor
a,b,n = map(int,input().split())
ans = 0
if n <= b:
    for i in range(n+1):
        ans = max(ans,floor(a*i/b) - a*floor(i/b))
else:
    for i in range(max(0,b-10),min(n,b+10)):
        ans = max(ans,floor(a*i/b) - a*floor(i/b))
print(ans)

### FIXED CODE ###

from math import floor
a,b,n = map(int,input().split())
ans = 0
if n <= b:
    for i in range(max(0,n-9),n+1):
        ans = max(ans,floor(a*i/b) - a*floor(i/b))
else:
    for i in range(max(0,b-10),min(n,b+10)):
        ans = max(ans,floor(a*i/b) - a*floor(i/b))
print(ans)
### BUGGY CODE ###

N=int(input())
P=[0]+list(map(float,input().split()))

DP=[[0]*(N+1) for _ in range(N+1)]
DP[0][0]=1

for i in range(N):
    for j in range(i+1):
        DP[i+1][j+1]+=DP[i][j]*P[i+1]
        DP[i+1][j]+=DP[i][j]*(1-P[i+1])

#for row in range(N+1):
    #string=''
    #for column in range(N+1):
        #string+=str(DP[row][column])+' '
    #print(string)

ans=0
half=(N+1)//2
for k in range(half,N+1):
    ans+=DP[N][k]

print(ans)

### FIXED CODE ###

N=int(input())
P=[0]+list(map(float,input().split()))

DP=[[0]*(N+1) for _ in range(N+1)]
DP[0][0]=1

for i in range(N):
    for j in range(i+1):
        DP[i+1][j+1]+=DP[i][j]*P[i+1]
        DP[i+1][j]+=DP[i][j]*(1-P[i+1])

#for row in range(N+1):
    #string=''
    #for column in range(N+1):
        #string+=str(DP[row][column])+' '
    #print(string)

ans=0
half=(N+1)//2
for k in range(half,N+1):
    ans+=DP[N][k]

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

s = list(input())
K = int(input())
character = '0abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
limit = len(s) - 1

here = 0
while K:
    tmp = character.find(s[here])
    if tmp == 1:
        pass
    elif tmp + K > 26 and here != limit:
        K -= 26 - tmp + 1
        s[here] = 'a'
        here += 1
    elif here == limit:
        K %= 26
        s[-1] = character[tmp + K]
        break
    else:
        here += 1
print(''.join(s))

### FIXED CODE ###

s = list(input())
K = int(input())
character = '0abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
limit = len(s) - 1

here = 0
while K:
    tmp = character.find(s[here])
    if tmp == 1 and here != limit:
        here += 1
        continue

    if tmp + K > 26 and here != limit:
        K -= 26 - tmp + 1
        s[here] = 'a'
        here += 1
    elif here == limit:
        K %= 26
        s[-1] = character[tmp + K]
        break
    else:
        here += 1
print(''.join(s))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
removal=0
B=set(A)
for i in B:
  if A.count(i)-i<0:
    removal+=A.count(i)
  else:
    removal+=A.count(i)-i
print(removal)
  


### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
removal=0
B=set(A)
for i in B:
  m=(bisect.bisect_right(A,i)-bisect.bisect_left(A,i))
  if m-i<0:
    removal+=m
  else:
    removal+=m-i
print(removal)
### BUGGY CODE ###

N = int(input())
S = input()
lst = []
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if not S[i]+S[j]+S[k] in lst:
                lst.append(S[i]+S[j]+S[k])
print(len(lst))

### FIXED CODE ###

N = int(input())
S = input()

s = set()
L = [[set() for i in range(2)] for j in range(N+1)]

ans = set()

for i in range(N):
    L[i+1][0].add(S[i])
    for k in L[i][0]:
        L[i+1][0].add(k)
        L[i+1][1].add(k + S[i])
    for k in L[i][1]:
        L[i+1][1].add(k)
        ans.add(k + S[i])

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

n,k = map(int,input().split())
while n > abs(n-k):
  n = abs(n-k)
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
n = n%k
while n > abs(n-k):
  n = abs(n-k)
print(n)
### BUGGY CODE ###

N = int(input())

coins = list(map(float, input().split()))

dp = [[0 for i in range(N+1)] for j in range(N)]

dp[0][0] = 1 - coins[0]
dp[0][1] = coins[0]

for j in range(1, N):
    for h in range(j+2):
        if h == 0:
            dp[j][h] = (1 - coins[j]) * dp[j-1][0]
        else:
            dp[j][h] = (1 - coins[j]) * dp[j-1][h] + coins[j] * dp[j-1][h-1]
     
print(sum(dp[-1][head] for head in range(N//2 + 1, N+1)))


### FIXED CODE ###

N = int(input())

coins = list(map(float, input().split()))

dp = [[0 for i in range(N+1)] for j in range(N)]

dp[0][0] = 1 - coins[0]
dp[0][1] = coins[0]

for j in range(1, N):
    for h in range(j+2):
        if h == 0:
            dp[j][h] = (1 - coins[j]) * dp[j-1][0]
        else:
            dp[j][h] = (1 - coins[j]) * dp[j-1][h] + coins[j] * dp[j-1][h-1]
     
print(sum(dp[-1][head] for head in range(N//2 + 1, N+1)))
### BUGGY CODE ###

import copy
n, q = map(int, input().split())
ab = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

ad_list = [[] for _ in range(n)]
for a, b in ab:
  ad_list[a].append(b)

count = [0 for _ in range(n)]

def dfs(v, x):
  count[v] += x
  ad = copy.deepcopy(ad_list)
  while len(ad[v]) != 0:
    ad_v = ad[v].pop()
    dfs(ad_v, x)
    if len(ad[v]) == 0:
      break

for p, x in px:
  dfs(p-1, x)

print(*count)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)
### BUGGY CODE ###

N = int(input())
hList = list(map(int, input().split()))
count = 0
nList = [ i + hList[i] for i in range(len(hList))]

for i in range(N):
  tmpVal = i - hList[i]
  count += nList.count(tmpVal)

print(count)

### FIXED CODE ###

import collections

N = int(input())
hList = list(map(int, input().split()))
count = 0
n_p = collections.Counter([ i + hList[i] for i in range(len(hList))])

for i in range(N):
  if i - hList[i] > 0:
    count += n_p.get(i - hList[i], 0)

print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
for i in range(n,m):
    if m%i:continue
    print(m//i);exit()
print(1)


### FIXED CODE ###

n,m=map(int,input().split())
ans=1
ps=[]
for i in range(1,int(m**(1/2))+1):
    if m%i:continue
    if n*(i)<=m:ans=max(i,ans)
    if n*(m//i)<=m:ans=max(ans,m//i)
print(ans)
### BUGGY CODE ###

# O(MN + 4^N) 解
# 参考: https://twitter.com/ei1333/status/1177951676818325504
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    dp = [float("inf")] * (1<<N)
    for _ in range(M):
        a, _ = map(int, input().split())
        C = list(map(int, input().split()))
        s = 0
        for c in C:
            s |= 1 << c-1
        dp[s] = min(dp[s], a)
    for i in range(1<<N):
        for j in range(1<<N):
            dp[i|j] = min(dp[i|j], dp[i]+dp[j])
    ans = dp[-1]
    print(ans if ans!=float("inf") else -1)

main()


### FIXED CODE ###

N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new
#print(dp)
ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)
### BUGGY CODE ###

N = int(input())
S = input()

for length_s in range(N//2, 0, -1):
    for start_s in range(0, N-length_s):
        check_s = S[start_s:start_s+length_s]
        if check_s in S[start_s+length_s:]:
            print(length_s)
            exit()
print(0)


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
len_s = 1
for i in range(N):
    tmp_s = S[i:i+len_s]
    while tmp_s in S[i+len_s:]:
        len_s += 1
        tmp_s = S[i:i+len_s]
        ans += 1
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
MOD = 10**9+7



dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 <= N and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD
print(dp[-1]%MOD)


### FIXED CODE ###

N,M = map(int,input().split())
A = set([int(input()) for i in range(M)])
MOD = 10**9+7

if 0 in A:
    print(0)
    exit()

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 <= N and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD
print(dp[-1])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0] * (n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def get(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s


    N,Q = map(int,input().split())
    C = list(map(int,input().split()))
    LR = [list(map(int,input().split()))+[i] for i in range(Q)]
    LR.sort(key=lambda x: x[1])
    bit = BIT(N)
    stone = [0]*(N+1)
    cur = 1
    ans = [0]*(Q)
    for l,r,i in LR:
        for j in range(cur,r+1):
            c = C[j-1]
            if stone[c]:
                bit.add(stone[c],-1)
            stone[c] = j
            bit.add(stone[c],1)
        ans[i] = bit.get(r)-bit.get(l-1)
    for a in ans:
        print(a)
main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0]*(n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = [0]*Q
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    cur = 1
    for q in query:
        l,r,j = q
        #良い玉の情報を更新する
        for i in range(cur,r+1):
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
        cur = r + 1
        ans[j]=bit.sum(r)-bit.sum(l-1)

    print(*ans, sep="\n")
main()
### BUGGY CODE ###

from collections import defaultdict
s = input()
t = input()
s_dic = defaultdict()
t_dic = defaultdict()


def iter(string, dic):
    for i in range(len(string)):
        if string[i] in dic.keys():
            dic[string[i]] += 1
        else:
            dic[string[i]] = 1
    return dic


s_pattern = iter(s, s_dic)
t_pattern = iter(t, t_dic)


def check(string, original):
    count = 0
    length = len(string)
    flag = False
    while 1:
        if string == original:
            flag = True
            break
        if count == length:
            flag = False
            break
        last = string[-1]
        string = last + string[:-1]
    return flag


if s_pattern != t_pattern:
    print('No')
else:
    if check(s, t):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

from collections import Counter
s = input()
t = input()


s_pattern = Counter(s)
t_pattern = Counter(t)


def check(string, original):
    n = len(string)
    flag = False
    for i in range(n):
        if original == string[i:] + s[:i]:
            flag = True
            break
    return flag


if s_pattern != t_pattern:
    print('No')
else:
    if check(s, t):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import deque
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(node)

Visited = [False for _ in range(n+1)]
Visited[node] = True
Visited_to = [[] for _ in range(n+1)]

Colors = [x for x in range(1, max_edges+1)]
Edge_colors = [[-1 for _ in range(n+1)] for _ in range(n+1)]


while dq:
    Colors_copy = copy.deepcopy(Colors)    
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    Visited_from = Visited_to[node]
    for v in Visited_from:
        Colors_copy.remove(Edge_colors[node][v])

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited_to[next_node].append(node)
        Visited[next_node] = True
        Edge_colors[node][next_node] = Colors_copy[0]
        Edge_colors[next_node][node] = Colors_copy[0]
        del Colors_copy[0]

print(max_edges)
for ab in AB:
    print(Edge_colors[ab[0]][ab[1]])

### FIXED CODE ###

from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)
### BUGGY CODE ###

N = int(input())
Hs = list(map(int, input().split()))
res = [0] * N

for index, h in enumerate(Hs):
    l = 0
    #if index > 0:
    #    l = max(res[index - 1] - 1, 0)

    tmp = h
    while index + l + 1 < N and tmp >= Hs[index + l + 1]:
        tmp = Hs[index + l + 1]
        l += 1
    res[index] = l

print(max(res))

### FIXED CODE ###

N = int(input())
Hs = list(map(int, input().split()))
res = [0] * N

for index, h in enumerate(Hs):
    l = 0
    if index > 0:
        l = max(res[index - 1] - 3, 0)

    tmp = h
    while index + l + 1 < N and tmp >= Hs[index + l + 1]:
        tmp = Hs[index + l + 1]
        l += 1
    res[index] = l

print(max(res))
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(M)]
V = [x for x in range(N+1)]
total = N * (N-1) // 2

def find(A, x):
    parent = A[x]
    if parent == x: return x
    root = find(A, parent)
    A[x] = root
    return root

def union(A, x, y):
    root, second = find(A, x), find(A, y)
    if root > second:
        second, root = root, second
    A[second] = root

conv = 0
answer = []
for a, b in AB[::-1]:
    answer.append(total - conv)
    root_A = find(V, a); root_B = find(V, b)
    if root_A != root_B:
        conv += V.count(root_A) * V.count(root_B)
        union(V, a, b)
        V = [find(V, x) for x in V]

for x in answer[::-1]:
    print(x)


### FIXED CODE ###

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
root = [i for i in range(N+1)]
comp_size = [1] * (N+1)

def find_root(x):
    a = root[x]
    if a == x:
        return x
    y = find_root(a)
    root[x] = y
    return y

def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root(y)
  root[x] = z
  return z

def merge(x, y):
    rx = find_root(x)
    ry = find_root(y)
    if rx == ry:
        return 0
    sx = comp_size[rx]
    sy = comp_size[ry]
    if sx >= sy:
        root[ry] = rx
        comp_size[rx] += sy
    else:
        root[rx] = ry
        comp_size[ry] += sx
    return sx * sy

result = N * (N-1) // 2
answer = []
for x, y in edges[::-1]:
    answer.append(result)
    result -= merge(x, y)

for r in answer[::-1]:
    print(r)