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 Die alone ”.

You have to handle Q queries; which consist of two survivors becoming friends and thereby uniting there 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 
the groups involving survivor A and survivor B unite into a larger group.

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
tanjiro_59: 2021-11-17 01:21:01

TLE if using Python. Python doesnt support multiset likely STL library. In stead using dict + heapq

[NG]: https://www.spoj.com/ranks/LOSTNSURVIVED/lang=PYTH%203.2.3
BTW. my solution has no log factors on any structures used.

Last edit: 2021-11-17 03:54:20
aditya04848spo: 2021-05-26 17:41:38

WA on test 6?
check on this test
1 1
1 1

correct ans is 0

and yes python3 passing

shubham_it_bit: 2020-05-05 09:26:21

easy one :)
cout ->0.45
printf->0.07
....hope someone can optimise it better using these tricks XD

robosapien: 2020-04-26 23:58:37

@mortiferum If solution with map works then solution with unordered_map should work better.. given your approach is optimal.

mortiferum: 2019-11-18 18:23:33

When trying to solve it using unordered_map i've always ended up getting TLE.
It seems to be veeter to just use two arrays for storing everything.

On my local computer the solution using unordered_map was as fast but maybe the pc on the cluster behaves a bit different.

Last edit: 2019-11-18 18:25:32
adityaxxx: 2019-02-11 07:13:53

Weak test cases

satyabrat35: 2019-02-09 15:04:42

Use set_pair
Great tv series btw .. :)

ongchuviettel: 2018-08-31 10:40:26

anyone here accepted by using python 3 :(. I got time limit :(

seyed37: 2018-03-01 08:49:17

SIMPLE BADIHIJAT
AC IN ONE GO

roham1381: 2018-03-01 08:45:25

Last edit: 2018-03-01 08:56:17

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 COFFEE DART FORTH GOSU JS-MONKEY KTLN OCT PROLOG R RACKET SQLITE SWIFT UNLAMBDA
Resource:codemonk- hackerearth