题目描述

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

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

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

输入格式

第一行两个整数 $n,m$。

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

接下来若干行，每行三个整数 $c,a,b$。

若 $c=0$，表示永久删除 $a,b$ 之间的边；

若 $c=1$，表示询问 $a,b$ 之间的桥的数量；

若 $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

数据规模与约定

记询问的次数为 $q$。

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

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^4$，$1\leq m\leq 10^5$，$1\leq q\leq 4\times 10^4$。