LOSTNSURVIVED - Lost and survived


On September 22, 2004, Oceanic Flight 815 crashed on a mysterious island somewhere in the pacific.

There actually were survivors in the crash, N survivors. The mysterious island kept on moving in space - time, so no rescue reached them.

Initially every survivor was on his own. But soon they realized there are these “The Others” (Scientists of damn Dharma Initiative) on this Island too.

So to protect themselves from mad Scientists they started uniting into groups after Dr. Shephard said “Live together or die alone”.

You have to handle Q queries; which consist of two survivors becoming friends and thereby uniting their respective groups into a larger group.

After each query, output the difference between the group of largest size and group of smallest size at that time.

If there is only one group, output 0. At first, everyone is in their own group.

Also note, if the two survivors in the query are already in the same group, print the current answer, and skip merging groups.

Also do comment if you have watched Lost :-p

Input

The first line consists of two space separated integers, N and Q

The next Q line consists of two integers, A and B, meaning that

survivor A and survivor B became friends uniting there groups.

Output

Output Q lines, the answer after each query.

1<=N<=100000

1<=Q<=100000

Example

Input:
5 3
1 2
2 3
5 4

Output:
1
2
1

hide comments
anmoldua: 2017-09-13 21:51:05

an easy stl(multiset) problem

steady_bunny: 2017-05-26 05:06:11

STL !!!! <3

nky_007: 2017-03-13 19:14:06

good question on DSU..

rraj001: 2016-08-20 04:55:37

good question :DSU and STL :)
similar question on hackerearth

Last edit: 2017-01-22 05:43:45
Deepak : 2016-02-04 18:56:37

DSU ;) + STL ...AC in one go...nice one..

kartikay singh: 2016-02-02 17:13:29

DSU:-)
Those are getting TLEs.
use iterative approach and scanf and printf

shubham_goyal: 2016-02-01 06:13:54

<snip> Can i get the test cases for which my code is wrong?

Last edit: 2022-06-19 13:16:48
varun yadav: 2016-01-28 15:39:50

AC in one go,, should be moved to tutorial :p

narutorocks: 2016-01-27 19:58:59

similar question on hackerearth

Urjit Patel: 2016-01-24 07:44:35

more test case pls!!
getting WA on test case #6


Added by:Umang Malhotra
Date:2016-01-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA
Resource:codemonk- hackerearth