#P2542. [AHOI2005] 航线规划
[AHOI2005] 航线规划
题目描述
对 Samuel 星球的探险已经取得了非常巨大的成就,于是科学家们将目光投向了 Samuel 星球所在的星系——一个巨大的由千百万星球构成的 Samuel 星系。
星际空间站的 Samuel II 巨型计算机经过长期探测,已经锁定了 Samuel 星系中 个星球的空间坐标,并对这些星球以 至 依次编号。
一些先遣飞船已经出发,在星球之间开辟探险航线。
探险航线是双向的,例如从 号星球到 号星球开辟探险航线,那么从 号星球到 号星球也可以使用这条航线。
例如下图所示:
在 个星球之间,有 条探险航线。
两星球之间,如果某条航线不存在,就无法从 星球抵达 星球,我们则称这条航线为关键航线。
显然上图中, 号与 号星球之间的关键航线有 条:即为 航线。
然而,在宇宙中一些未知的磁暴和行星的冲撞,使得已有的某些航线被破坏,随着越来越多的航线被破坏,探险飞船又不能及时恢复这些航线,可见两个星球之间的关键航线会越来越多。
假设在上图中,航线 (从 号星球到 号星球)被破坏。此时, 号与 号星球之间的关键航线就有 条:,,。
小联的任务是,不断关注航线被破坏的情况,并随时给出两个星球之间的关键航线数目。现在请你帮助完成。
输入格式
第一行有两个整数,分别表示星球个数 和初始时的航线条数 。
接下来 行,每行有两个不相同的整数 ,表示星球 和星球 之间存在一条航线。
接下来有若干行,每行首先给出一个整数 ,表示一次操作的类型。
- 若 ,则后接两个整数 ,表示询问当前 两星球之间有多少关键航线。
- 若 ,则后接两个整数 ,表示 之间的航线被破坏。
- 若 ,则表示输入结束,后面不再存在操作。
输出格式
对每个 的询问,输出一行一个整数表示关键航线数目。
5 5
1 2
1 3
3 4
4 5
4 2
1 1 5
0 4 2
1 5 1
-1
1
3
提示
数据规模与约定
对于全部的测试点,保证:
- ,。
- ,。
- 无论航线如何被破坏,任意时刻任意两个星球都能够相互到达。在整个数据中,任意两个星球之间最多只可能存在一条直接的航线。
- 对于 的操作,保证操作前航线 存在。
- 询问与破坏航线的总次数不超过 。