/****************************************\
* Author : ztx
* Title : [AHOI2005]LANE 航线规划
* ALG : Tarjan+LCT+离线+瞎搞
* CMT : "无论航线如何被破坏，任意时刻任意两个星球都能够相互到达":
* 连通图,缩点后不是森林
* "在整个数据中，任意两个星球之间最多只可能存在一条直接的航线":
* 无重边
* Time :
\****************************************/
/****************************************\
* Author : ztx
* Title : [AHOI2005]LANE 航线规划
* ALG : Tarjan+LCT+离线+瞎搞
* CMT : "无论航线如何被破坏，任意时刻任意两个星球都能够相互到达":
* 连通图,缩点后不是森林
* "在整个数据中，任意两个星球之间最多只可能存在一条直接的航线":
* 无重边
* Time :
\****************************************/
#include <cstdio>
int CH , NEG ;
inline int GETCHAR() {
static const int LEN = 1<<15 ;
static char BUF[LEN] , *S = BUF , *T = BUF ;
if (S == T) {
T = (S=BUF)+fread(BUF , 1 , LEN , stdin) ;
if (S == T) return EOF ;
}
return *S ++ ;
}
inline void read(int& ret) {
ret = NEG = 0 ; while (CH=GETCHAR() , CH<'!') ;
if (CH == '-') NEG = true , CH = GETCHAR() ;
while (ret=(ret<<1)+(ret<<3)+CH-'0' , CH=GETCHAR() , CH>'!') ;
if (NEG) ret = -ret ;
}
#include <algorithm>
#include <cstring>
#define maxn 30010LL
#define maxm 1000010LL
#define maxe 2000010LL
#define maxq 40010LL
#define infi 0x3f3f3f3fLL
int n , m , Q ;
struct FST { int to , next ; } e1[maxe] , e2[maxe] ;
int star1[maxn] = {0} , star2[maxn] = {0} , tote1 = 0 , tote2 = 0 ;
void AddEdge(int u , int v) {
e1[++tote1].to = v ; e1[tote1].next = star1[u] ; star1[u] = tote1 ;
e1[++tote1].to = u ; e1[tote1].next = star1[v] ; star1[v] = tote1 ;
}
void BCCAddEdge(int u , int v) {
e2[++tote2].to = v ; e2[tote2].next = star2[u] ; star2[u] = tote2 ;
e2[++tote2].to = u ; e2[tote2].next = star2[v] ; star2[v] = tote2 ;
}
struct QUE { int cmd , u , v , id , ans ; } q[maxq] ;
struct EDGE { int u , v , del ; EDGE() { del = false ; } } e[maxm] ;
int tote = 0 ;
bool CmpT(const EDGE& a , const EDGE&b) {
if (a.u == b.u) return a.v < b.v ;
return a.u < b.u ;
}
int L , M , R ;
inline int Bsearch(int u , int v) {
L = 1 , R = m ;
while (R-L > 1) {
/* (L , R] */
M = L+(R-L)/2 ;
if (e[M].u<u || (e[M].u==u&&e[M].v<v)) L = M ;
else R = M ;
}
return R ;
}
int f[maxn] = {0} ;
inline int GetAnc(int u) { return f[u] ? f[u] = GetAnc(f[u]) : u ; }
inline void Union(int u , int v) {
u = GetAnc(u) , v = GetAnc(v) ;
if (u != v) f[u] = v ;
}
int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int size[maxn] = {0} ;
bool rev[maxn] = {0} ;
#define null 0LL
#define left(u) ch[u][0]
#define right(u) ch[u][1]
template<typename T>inline void Exchange(T&a , T&b) { T c=a;a=b;b=c; }
inline bool Isrt(int u) { fa[u] = GetAnc(fa[u]) ; return (fa[u]==null)||(left(fa[u])!=u&&right(fa[u])!=u) ; }
inline void Maintain(int u) {
size[u] = 1 ;
if (left(u)) size[u] += size[left(u)] ;
if (right(u)) size[u] += size[right(u)] ;
}
inline void Clear(int u) {
if (!u) return ;
if (!Isrt(u)) Clear(fa[u]) ;
if (rev[u]) {
rev[u] = false ;
rev[left(u)] ^= true ;
rev[right(u)] ^= true ;
Exchange(left(u) , right(u)) ;
}
}
inline void zig(int x) {
/* right rotate */
int y = fa[x] = GetAnc(fa[x]) , z = fa[y] = GetAnc(fa[y]) ;
if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
fa[right(x)] = y ; left(y) = right(x) ; fa[y] = x ; right(x) = y ;
Maintain(y) , Maintain(x) ;
}
inline void zag(int x) {
/* left rotate */
int y = fa[x] = GetAnc(fa[x]) , z = fa[y] = GetAnc(fa[y]) ;
if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
fa[left(x)] = y ; right(y) = left(x) ; fa[y] = x ; left(x) = y ;
Maintain(y) , Maintain(x) ;
}
inline void Splay(int x) {
Clear(x) ;
int y , z ;
while (!Isrt(x)) {
y = fa[x] = GetAnc(fa[x]) , z = fa[y] = GetAnc(fa[y]) ;
if (Isrt(y)) {
if (left(y) == x) zig(x) ; else zag(x) ;
} else {
if (left(z) == y) {
if (left(y) == x) zig(x) , zig(x) ;
else zag(x) , zig(x) ;
} else if (right(z) == y) {
if (right(y) == x) zag(x) , zag(x) ;
else zig(x) , zag(x) ;
}
}
}
}
inline void Access(int u) {
for (int v = null ; u ; u = fa[u] = GetAnc(fa[u])) Splay(u) , right(u) = v , v = u , Maintain(u) ;
}
inline void Makeroot(int u) {
Access(u) , Splay(u) , rev[u] ^= true ;
}
int DFN[maxn] = {0} , LOW[maxn] = {0} , Belong[maxn] = {0} ;
int Stap[maxn] = {0} ;
int Stop , Bcnt , Dindex ;
void DFS(int from , int u) {
int v = 0 ;
DFN[u] = LOW[u] = ++Dindex , Stap[++Stop] = u ;
for (int p = star1[u] ; p ; p = e1[p].next) {
v = e1[p].to ;
if (from == v) continue ;
if (!DFN[v]) {
DFS(u , v) ; if (LOW[u] > LOW[v]) LOW[u] = LOW[v] ;
if (DFN[u] < LOW[v]) {
Bcnt ++ ;
for ( ; Stap[Stop]!=v ; ) {
Belong[Stap[Stop--]] = Bcnt ;
}
if (Stap[Stop]==v) Belong[Stap[Stop--]] = Bcnt ;
}
} else if (LOW[u] > DFN[v]) LOW[u] = DFN[v] ;
}
}
void Tarjan() {
Stop = Bcnt = Dindex = 0 ;
memset(DFN , 0 , sizeof(DFN)) ;
DFS(0 , 1) ;
Bcnt ++ ; while (Stop) Belong[Stap[Stop--]] = Bcnt ;
}
bool vis[maxn] = {0} ;
void BuildTree(int u) {
if (vis[u]) return ; vis[u] = size[u] = 1 ;
int p , v ;
for (p = star2[u] ; p ; p = e2[p].next) {
v = e2[p].to ;
if (!vis[v]) {
fa[v] = u ; BuildTree(v) ;
}
}
}
void Shrink(int from , int u) {
if (!u) return ;
if (from) Union(from , u) ;
if (left(u)) Shrink(u , left(u)) ;
if (right(u)) Shrink(u , right(u)) ;
}
int i , j , u , v , k , cnt = 0 ;
int main() {
#define READ
#ifdef READ
freopen("lane.in" ,"r",stdin ) ;
freopen("lane.out","w",stdout) ;
#endif
/* 读入 */
read(n) , read(m) ;
for (i = 1 ; i <= m ; i ++ ) {
read(e[i].u) , read(e[i].v) ;
if (e[i].u > e[i].v) Exchange(e[i].u , e[i].v) ;
}
/* 标记删除边 */
std::sort(e+1 , e+m+1 , CmpT) ;
for (Q = 0 ; true ; ) {
read(q[Q+1].cmd) ;
if (q[Q+1].cmd == -1) break ;
Q ++ ; read(q[Q].u) , read(q[Q].v) ;
if (q[Q].cmd == 0) {
if (q[Q].u > q[Q].v) Exchange(q[Q].u , q[Q].v) ;
e[Bsearch(q[Q].u , q[Q].v)].del = true ;
}
}
/* 对最终状态建图 */
for (i = 1 ; i <= m ; i ++ ) {
if (e[i].del) continue ;
AddEdge(e[i].u , e[i].v) ;
}
/* Tarjan求双联通分量 */
Tarjan() ;
/* 对缩点后的联通块建图 */
for (i = 1 ; i <= m ; i ++ ) {
if (e[i].del) continue ;
u = Belong[e[i].u] , v = Belong[e[i].v] ;
if (u != v) BCCAddEdge(u , v) ;
}
/* 对联通块建树 */
BuildTree(1) ;
/* 回答询问 */
for (i = Q ; i ; i -- ) {
u = GetAnc(Belong[q[i].u]) , v = GetAnc(Belong[q[i].v]) ;
if (q[i].cmd == 1) {
if (u == v) q[i].ans = 0 ;
else {
Makeroot(u) ; Access(v) , Splay(v) ; q[i].ans = size[v]-1 ;
}
} else if (u != v) {
Makeroot(u) ; Access(v) , Splay(v) ; Shrink(null , v) ; fa[GetAnc(v)] = null ;
}
}
for (i = 1 ; i <= Q ; i ++ )
if (q[i].cmd == 1) printf("%d\n", q[i].ans ) ;
#ifdef READ
fclose(stdin) ; fclose(stdout) ;
#else
getchar() ; getchar() ;
#endif
return 0 ;
}
/*
9 10
1 2
2 3
2 4
2 6
3 5
3 6
4 6
4 8
6 7
7 9
1 1 7
-1
20 35
1 2
1 3
1 4
1 8
1 11
1 16
2 3
2 5
2 7
2 11
2 19
3 8
3 9
3 10
4 6
4 9
4 11
4 15
4 19
5 8
5 11
5 16
5 17
6 12
6 14
6 16
7 10
7 11
7 13
7 19
8 9
9 18
10 14
14 20
17 18
0 8 9
0 1 8
1 7 20
1 5 15
1 12 14
0 6 16
1 14 8
1 17 2
0 6 14
1 5 6
0 17 18
1 14 9
-1
*/
评论 (0)