2019-11-24 20:58:20

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}

const int N=1000000+10,M=2000000+10,L=100000;

int n,m;

int fa[N],sz[N],sta[N],top=0;
inline int find(int x) { return x==fa[x]?x:find(fa[x]); }
inline void merge(int x,int y) {
x=find(x),y=find(y);
if (x==y) return;
if (sz[x]>sz[y]) swap(x,y);
fa[x]=y,sz[y]+=sz[x],sta[++top]=x;
}
inline void undo(int pos) {
while (top>pos) { int x=sta[top--]; sz[fa[x]]-=sz[x],fa[x]=x; }
}

#define ls (o<<1)
#define rs (o<<1|1)
vector<pair<int,int> > vec[L<<2];
inline void modify(int o,int l,int r,int ql,int qr,pair<int,int> e) {
if (ql<=l&&r<=qr) { vec[o].push_back(e); return; }
int mid=(l+r)>>1;
if (ql<=mid) modify(ls,l,mid,ql,qr,e);
if (qr>mid) modify(rs,mid+1,r,ql,qr,e);
}
inline void solve(int o,int l,int r) {
int tmp=top;
for (re auto i:vec[o]) merge(i.first,i.second);
if (l==r) {
if (sz[find(1)]==n) { printf("%d\n",l); exit(0); }
} else {
int mid=(l+r)>>1;
solve(ls,l,mid),solve(rs,mid+1,r);
}
undo(tmp);
}
#undef ls
#undef rs

int main() {
}