bzoj#P2896. 桥

题目描述

有一张 nn 个点 mm 条边的无向图,如果去掉某条边后,图中 a,ba,b 两点不可互达,那么我们称这条边是 a,ba,b 两点间的桥。

现在我们随时有可能永久删除某条边,或者询问你某两点间有几条边是桥,请你做出回答。

另外任意时刻我们都会保持图的连通性,这点你放心。

输入格式

第一行两个整数 n,mn,m

接下来 mm 行每行两个整数 u,vu,v 表示 u,vu,v 之间的一条无向边。

接下来若干行,每行三个整数 c,a,bc,a,b

c=0c=0,表示永久删除 a,ba,b 之间的边;

c=1c=1,表示询问 a,ba,b 之间的桥的数量;

c=1c=-1,表示询问结束。

输出格式

对于每个询问,输出一行一个整数表示答案。

5 5
1 2
1 3
3 4
4 5
4 2
1 1 5
0 4 2
1 5 1
-1
1
3

数据规模与约定

记询问的次数为 qq

对于 30%30\% 的数据,1n,m,q1031\leq n,m,q\leq 10^3

对于 100%100\% 的数据,1n3×1041\leq n\leq 3\times 10^41m1051\leq m\leq 10^51q4×1041\leq q\leq 4\times 10^4