题面

有\(n\)个点，\(m\)条边的不联通图。一一加入\(p\)条边，每加入一条就询问该边所在边双联通分量的点数。

• \(n,m,q\leq2*10^5\)

  解析

  该题解法与一题\(50pts\)算法有异曲同工之妙。

  怎样生成边双？在生成树上加一条边，边的两端点树上路径中的所有点互为边双。

于是先要构出一棵生成树。

先用并查集维护点之间的联通性，把\(m+p\)条边中的树边（边两端点不联通）连了，标记非树边。

然而图可能还是不联通，而只有几个大联通块。把它们与\(1\)结点相连即可。

生成树构建完毕。预处理一下点的父亲和深度，方便以后跑树上路径。

接下来开始针对非树边。（并查集要清空）

根据生成边双方法，我们应该把边的两端点树上路径中的所有点并入同一个并查集。

从深度大的端点开始，不断往上跳，将结点与结点父亲合并，同时统计并查集大小之和即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define re register#define il inline#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int N=5e5+100;struct Edge{int to,nxt;}e[N<<1];struct dat{int u,v,vis;}a[N<<1];int n,m,p,f[N],ff[N],d[N],sz[N],cnt,h[N];il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}il void Merge(re int u,re int v){ while(u^v) { if(d[u]