6896: BZOJ2896:桥

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

有一张N个点,M条边的无向图,如果去掉某条边后,图中A,B两点不可互达,那么我们称这条边是A,B两点间的桥。现在我们随时有可能永久删除某条边,或者询问你某两点间有几条边是桥,请你做出回答。另外任意时刻我们都会保持图的连通性,这点你放心。


输入格式

第一行n,m 接下来m行表示m条边 然后每行三个整数c,a,b如果c=0表示边ab被永久删除,如果c=1表示询问ab间有几条边是桥。如果c=-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
Data Limit
对于30%的数据,有1 ≤ N ≤ 1000,1 ≤ M ≤ 1000,询问数加删除数不多于1000.
对于100%的数据,有1 ≤ N ≤ 30000,1 ≤ M ≤ 100000,询问数加删除数不多于40000
 

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: