William arrived at a conference dedicated to cryptocurrencies. Networking, meeting new people, and using friends' connections are essential to stay up to date with the latest news from the world of cryptocurrencies.

The conference has $n$ participants, who are initially unfamiliar with each other. William can introduce any two people, $a$ and $b$, who were not familiar before, to each other.

William has $d$ conditions, $i$'th of which requires person $x_i$ to have a connection to person $y_i$. Formally, two people $x$ and $y$ have a connection if there is such a chain $p_1=x, p_2, p_3, \dots, p_k=y$ for which for all $i$ from $1$ to $k - 1$ it's true that two people with numbers $p_i$ and $p_{i + 1}$ know each other.

For every $i$ ($1 \le i \le d$) William wants you to calculate the maximal number of acquaintances one person can have, assuming that William satisfied all conditions from $1$ and up to and including $i$ and performed exactly $i$ introductions. The conditions are being checked after William performed $i$ introductions. The answer for each $i$ must be calculated independently. It means that when you compute an answer for $i$, you should assume that no two people have been introduced to each other yet.


-----Input-----

The first line contains two integers $n$ and $d$ ($2 \le n \le 10^3, 1 \le d \le n - 1$), the number of people, and number of conditions, respectively.

Each of the next $d$ lines each contain two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i$), the numbers of people which must have a connection according to condition $i$.


-----Output-----

Output $d$ integers. $i$th number must equal the number of acquaintances the person with the maximal possible acquaintances will have, if William performed $i$ introductions and satisfied the first $i$ conditions.


-----Examples-----

Input
7 6
1 2
3 4
2 4
7 6
6 5
1 7
Output
1
1
3
3
3
6
Input
10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4
Output
1
2
3
4
5
5
6
8


-----Note-----

The explanation for the first test case:

In this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that William introduced two connected people. The person marked with red has the most acquaintances. These are not the only correct ways to introduce people.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Implementation

Greedy algorithms

Tree algorithms

Spanning trees


Solutions:
(n, d) = map(int, input().split())
p = [-1] * (n + 1)
c = 0

def find(x):
	if p[x] < 0:
		return x
	return find(p[x])
for i in range(d):
	(x, y) = map(int, input().split())
	if find(x) == find(y):
		c += 1
	else:
		p[find(x)] += p[find(y)]
		p[find(y)] = find(x)
	a = sorted(p)
	ans = 0
	for j in range(c + 1):
		ans += a[j]
	print(-(1 + ans))


(n, d) = map(int, input().split())
pessoas = [-1] * (n + 1)
count = 0

def find(x):
	if pessoas[x] < 0:
		return x
	else:
		return find(pessoas[x])
for i in range(d):
	(x, y) = map(int, input().split())
	if find(x) == find(y):
		count += 1
	else:
		pessoas[find(x)] += pessoas[find(y)]
		pessoas[find(y)] = find(x)
	resposta = 0
	lista = sorted(pessoas)
	for j in range(count + 1):
		if lista[j] < 0:
			resposta += lista[j]
	print(-1 - resposta)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
(n, d) = M()
p = [-1] * (n + 1)
c = 0

def find(x):
	if p[x] < 0:
		return x
	return find(p[x])
for i in range(d):
	(x, y) = M()
	if find(x) == find(y):
		c += 1
	else:
		p[find(x)] += p[find(y)]
		p[find(y)] = find(x)
	ans = 0
	a = sorted(p)
	for j in range(c + 1):
		if a[j] < 0:
			ans += a[j]
	print(-1 - ans)


def dsu(par, i):
	if par[i] == i:
		return i
	return dsu(par, par[i])

def solve():
	(n, d) = map(int, input().split())
	par = [0] * (n + 1)
	ans = [1] * (n + 1)
	ct = 0
	for i in range(1, n + 1):
		par[i] = i
	for i in range(d):
		(x, y) = map(int, input().split())
		p1 = dsu(par, x)
		p2 = dsu(par, y)
		if p1 != p2:
			par[p2] = p1
			ans[p1] += ans[p2]
		else:
			ct += 1
		b = []
		for j in range(1, n + 1):
			if par[j] == j:
				b.append(ans[j])
		b.sort()
		b.reverse()
		s = 0
		for j in range(min(ct + 1, len(b))):
			s += b[j]
		print(s - 1)
	return 0
t = 1
while t > 0:
	t -= 1
	solve()


import sys
import math
from fractions import Fraction
from decimal import *
input = sys.stdin.readline
inp = input().strip()
arr = [int(x) for x in inp.split(' ')]
n = arr[0]
t = arr[1]
par = [0] + [i + 1 for i in range(n)]
sizes = [0] + [1 for i in range(n)]
extra = 0
while t > 0:
	inp = input().strip()
	arr = [int(x) for x in inp.split(' ')]
	x = arr[0]
	y = arr[1]
	px = x
	while par[px] != px:
		px = par[px]
	py = y
	while par[py] != py:
		py = par[py]
	if px == py:
		extra += 1
	else:
		par[py] = px
		sizes[px] += sizes[py]
		sizes[py] = -1
	cursizes = []
	for s in sizes[1:]:
		if s != -1:
			cursizes.append(s)
	cursizes.sort(key=lambda x: -x)
	i = 0
	for j in range(extra):
		cursizes[i + 1] += cursizes[i]
		i += 1
		if i == len(cursizes) - 1:
			break
	print(cursizes[i] - 1)
	t -= 1


from collections import defaultdict
n = 10 ** 3 + 10
parent = [i for i in range(n)]
size = [1 for i in range(n)]

def find(root):
	a = root
	while parent[a] != a:
		a = parent[a]
	while root != a:
		nextnode = parent[root]
		parent[root] = a
		root = nextnode
	return a

def union(a, b):
	a = find(a)
	b = find(b)
	if a != b:
		if size[a] < size[b]:
			(a, b) = (b, a)
		parent[b] = a
		size[a] += size[b]
		return False
	else:
		return True
c = 0
(l, d) = map(int, input().split())
for j in range(d):
	(a, b) = map(int, input().split())
	cans = union(a, b)
	if cans:
		c += 1
	ans = -1
	allp = set()
	grps = []
	for k in range(1, l + 1):
		pr = find(k)
		if pr not in allp:
			allp.add(pr)
			grps.append(size[pr])
	grps.sort(reverse=True)
	for k in range(min(c + 1, len(grps))):
		ans += grps[k]
	print(ans)


def dfs(people):
	count = 1
	people.color = 1
	for fr in people.friends:
		if fr.color != 1:
			count += dfs(fr)
	return count

def find(x, y):
	x.color = 1
	if x.num == y.num:
		return True
	for fr in x.friends:
		if fr.color != 1 and find(fr, y):
			return True
	return False

class People:

	def __init__(self, num):
		self.num = num
		self.friends = set()
		self.color = 0

	def add(self, friend):
		self.friends.add(friend)
		friend.friends.add(self)
(n, d) = map(int, input().split())
peoples = list()
for i in range(n):
	peoples.append(People(i))
more = 0
for i in range(d):
	(a, b) = map(int, input().split())
	if find(peoples[a - 1], peoples[b - 1]):
		more += 1
	else:
		peoples[a - 1].add(peoples[b - 1])
	for pl in peoples:
		pl.color = 0
	meets = list()
	for people in peoples:
		meets.append(dfs(people))
	meets.sort()
	print(sum(meets[len(meets) - more - 1:len(meets)]) - 1)
	for pl in peoples:
		pl.color = 0


import sys

def solve():
	inp = sys.stdin.readline
	(n, d) = map(int, inp().split())

	def getp(x):
		if P[x] == x:
			return x
		P[x] = getp(P[x])
		return P[x]
	e = [tuple(map(int, inp().split())) for i in range(d)]
	for i in range(1, len(e) + 1):
		P = list(range(n + 1))
		S = [1] * (n + 1)
		can = 0
		for j in range(i):
			a = getp(e[j][0])
			b = getp(e[j][1])
			if a != b:
				if S[a] < S[b]:
					(a, b) = (b, a)
				P[b] = a
				S[a] += S[b]
			else:
				can += 1
		W = [True] * (n + 1)
		q = []
		for j in range(1, n + 1):
			j = getp(j)
			if W[j]:
				W[j] = False
				q.append(S[j])
		ans = 0
		q.sort(reverse=True)
		for j in range(can + 1):
			ans += q[j]
		print(max(ans - 1, 1))

def main():
	solve()
main()