***City and Campers 2

City and Campers 2

Alex has split into N parts, and each of these N parts is wandering around the city aimlessly. You have to handle Qqueries; which consist of two groups of Alex's finding each other and becoming one larger group. After each query, output the minimum difference between two groups. If there is only one group, output 0. At first, everyone is in their own group. What this means is that there are N groups, each of which contain 1 part of Alex.

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

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 Alex A and Alex B find each other.

Output:

Output Q lines, the answer after each query.

Constraints:

1 <= N <= 10⁵

1 <= Q <= 10⁵

---

Sample Input

(Plaintext Link)

2 1
1 2

Sample Output

(Plaintext Link)

0

Explanation

The two groups merge to become one larger group, so the difference will be 0.

--------------------------------------------------------------------editorial---------------------------------------------------------------------

This problem can be solved using DSU. I shall be using this concept to explain my approach. If you are not familiar with the concept, please give the editorial of City and Floods a read to understand the basics of DSU.

This is pretty similar to City and Campers, but what makes the problem challenging, in my opinion, is that we are looking for the smallest, and not the largest difference between 2 sets. Like any DSU problem, we are given some disjoint sets initially where each set has a single element.

Here is a naive approach to the problem. Simply keep track of sizes of each disjoint set. Then in O(n^2), find the minimum difference between sizes of two sets, but we have a very large number of queries, q. So, this solution would time out.

An improvement would be store the sizes in some data structure that C++ STL provides, like set or multiset and iterate over the whole set in O(n) to get the minimum difference in the sizes of two disjoint sets. This is still O(n*q) and would time out.

An even better improvement would be to also store tuples which holds 3 values, (representative 1, representative2, abs(representative1.size - representative2.size)). If this can be ordered by the 3rd value, i.e., abs(representative1.size - representative2.size), then each query can be answered in O(1) for obtaining the value + O(log n) if you use sets/multisets for keeping track of the current tuples. So, this reduces to O(q*(log n)).

--------------------------------------------------------------code-----------------------------------------------------------------------

/*
*/

//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <ctime> 

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

using namespace std;


int n,m,w[1<<20],sz[1<<20];
set<int> S;
multiset<int> I;
map<int, int> cnt;
int ans;

int get(int x)
{
if (x==w[x])
return x;
return w[x]=get(w[x]);
}

set<int>::iterator it;

void remove_number(int x)
{
S.erase(x);
it=S.lower_bound(x);
int val=(*it);
--it;
int val2=(*it);
//cout<<val<<" "<<val2<<endl;
//cout<<val-x<<" "<<x-val2<<" "<<I.size()<<endl;
I.erase(I.find(val-x));
I.erase(I.find(x-val2));
I.insert(val-val2);
}

void add_number(int x)
{
it=S.lower_bound(x);
int val=(*it);
--it;
int val2=(*it);
// cout<<val<<"@"<<val2<<endl;
I.erase(I.find(val-val2));
I.insert(val-x);
I.insert(x-val2);
S.insert(x);
}
multiset<int> D;

void merge(int a,int b)
{
w[a]=b;
// cout<<"@"<<endl;

D.erase(D.find(cnt[sz[a]]));
--cnt[sz[a]];
if (cnt[sz[a]])
D.insert(cnt[sz[a]]);

// D.insert(sz[a]+sz[b]);
//cout<<"@"<<endl;
if (cnt[sz[a]]==0)
{
remove_number(sz[a]);
}
//cout<<"@"<<endl;
D.erase(D.find(cnt[sz[b]]));
--cnt[sz[b]];
if (cnt[sz[b]])
D.insert(cnt[sz[b]]);
if (cnt[sz[b]]==0)
remove_number(sz[b]);
sz[b]+=sz[a];
// cout<<"@"<<endl;
if (cnt[sz[b]]==0)
add_number(sz[b]);

// cout<<"@"<<endl;
if (cnt[sz[b]]>0)
D.erase(D.find(cnt[sz[b]]));
cnt[sz[b]]++;
D.insert(cnt[sz[b]]);
ans=(*I.begin());
if (*D.rbegin()>1)
ans=0;
}

int main(){
//freopen("blind.in","r",stdin);
//freopen("blind.out","w",stdout);
//freopen("F:/in.txt","r",stdin);
//freopen("F:/output.txt","w",stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin>>n>>m;

for (int i=1;i<=n;i++)
w[i]=i,
sz[i]=1;

S.insert(-1e9);
S.insert(1e9);
cnt[1]=n;
I.insert(2e9);
add_number(1);
ans=0;

D.insert(n);
int g=n;

//cout<<I.size()<<endl;

/*for (multiset<int>::iterator it=I.begin();it!=I.end();it++)
{
cout<<"*"<<(*it)<<endl;
}
*/
for (int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
a=get(a);
b=get(b);
if (a==b)
{
cout<<ans<<endl;
continue;
}
--g;
merge(a,b);
if (g==1)
ans=0;

cout<<ans<<endl;
}

return 0;}