#P2542. [AHOI2005] 航线规划

    ID: 1550 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2005线段树各省省选安徽O2优化强连通分量缩点最近公共祖先LCA树链剖分树剖

[AHOI2005] 航线规划

题目描述

对 Samuel 星球的探险已经取得了非常巨大的成就,于是科学家们将目光投向了 Samuel 星球所在的星系——一个巨大的由千百万星球构成的 Samuel 星系。

星际空间站的 Samuel II 巨型计算机经过长期探测,已经锁定了 Samuel 星系中 nn 个星球的空间坐标,并对这些星球以 11nn 依次编号。

一些先遣飞船已经出发,在星球之间开辟探险航线。

探险航线是双向的,例如从 11 号星球到 33 号星球开辟探险航线,那么从 33 号星球到 11 号星球也可以使用这条航线。

例如下图所示:

55 个星球之间,有 55 条探险航线。

A,BA,B 两星球之间,如果某条航线不存在,就无法从 AA 星球抵达 BB 星球,我们则称这条航线为关键航线。

显然上图中,11 号与 55 号星球之间的关键航线有 11 条:即为 454\leftrightarrow5 航线。

然而,在宇宙中一些未知的磁暴和行星的冲撞,使得已有的某些航线被破坏,随着越来越多的航线被破坏,探险飞船又不能及时恢复这些航线,可见两个星球之间的关键航线会越来越多。

假设在上图中,航线 424\leftrightarrow2(从 44 号星球到 22 号星球)被破坏。此时,11 号与 55 号星球之间的关键航线就有 33 条:131 \leftrightarrow 3343 \leftrightarrow 4454 \leftrightarrow 5

小联的任务是,不断关注航线被破坏的情况,并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

输入格式

第一行有两个整数,分别表示星球个数 nn 和初始时的航线条数 mm

接下来 mm 行,每行有两个不相同的整数 u,vu, v,表示星球 uu 和星球 vv 之间存在一条航线。

接下来有若干行,每行首先给出一个整数 opop,表示一次操作的类型。

  • op=1op = 1,则后接两个整数 u,vu, v,表示询问当前 u,vu, v 两星球之间有多少关键航线。
  • op=0op = 0,则后接两个整数 u,vu, v,表示 u,vu, v 之间的航线被破坏。
  • op=1op = -1,则表示输入结束,后面不再存在操作。

输出格式

对每个 op=1op = 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

提示

数据规模与约定

对于全部的测试点,保证:

  • 1n3×1041 \leq n \leq 3 \times 10^41m1051 \leq m \leq 10^5
  • 1op1-1 \leq op \leq 11u,vn1 \leq u, v \leq n
  • 无论航线如何被破坏,任意时刻任意两个星球都能够相互到达。在整个数据中,任意两个星球之间最多只可能存在一条直接的航线。
  • 对于 op=0op = 0 的操作,保证操作前航线 uvu \leftrightarrow v 存在。
  • 询问与破坏航线的总次数不超过 4×1044 \times 10^4