标签：最小生成树，并查集
小B准备设计施工方案。
设计图是一个n个点m条边的图，小B每次施工可以取图中一个还没有完工的生成森林把它完工。
为了加快施工效率，每次取的时候小B都会最大化当前这个生成森林的边数。请你帮他找出一个符合要求的施工方案。
如果有多个方案，输出任意一种即可。
输入格式
第一行两个整数n, m。
后面m行，每行两个数ai,bi表示一条边，保证没有自环。
输出格式
m行，每行一个整数，表示这条边属于第几次。如果有多个方案，输出任意一种即可。
样例一
input
5 7
1 2
2 3
3 4
4 5
1 2
2 3
1 2
output
1
1
1
1
3
2
2
限制与约定
分析
每条边加入图中，维护若干个森林，每条边都加入到第一个两个端点不连通的森林中
每一个生成森林都用并查集来维护，二分出第一个两端点不连通的并查集
时间复杂度为O（m log m*a(n)）
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define reg(i,a) for(int i=u[a];i;i=e[i].pre)
#define v e[i].to
#define LL long long
using namespace std;
const int maxn=1e6+10;
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct edge{int to,pre;}e[maxn<<1];
int u[maxn],l=1;
inline void ins(int a,int b){e[++l]=(edge){b,u[a]},u[a]=l;}
int id[maxn],n,m;
int pre[maxn*2],nxt[maxn*2],mx=0,r[maxn];
bool vis[maxn];
int del(int x){
nxt[pre[x]]=nxt[x];
pre[nxt[x]]=pre[x];
}
void insert(int x,int r){
pre[x]=maxn+r,nxt[x]=nxt[maxn+r];
pre[nxt[x]]=nxt[pre[x]]=x;
}
void add(int x) {
del(x);
r[x]++; mx = max(mx, r[x]);
insert(x, r[x]);
}
void Forest(){
rep(i,1,n)insert(i,0);
rep(i,1,n){
while(!nxt[maxn+mx])mx--;
int x=nxt[maxn+mx];del(x);vis[x]=true;
reg(i,x) if(!vis[v]) id[i>>1]=r[v]+1,add(v);
}
}
int main()
{
n=read(),m=read();
rep(i,1,m){
int a=read(),b=read();
ins(a,b),ins(b,a);
}
Forest();
rep(i,1,m) printf("%d\n",id[i]);
return 0;
}
