← 返回题目列表

Codeforces · 165/D

D. 胡子图

中文机器翻译题面 查看原题

让我们定义一个由 n 个顶点和 n - 1 条边组成的无向连通图作为胡子,如果它的所有顶点(也许除了 1 个)的度数都是 2 或 1(即,不存在超过 1 个度数大于 2 的顶点)。让我们提醒您,顶点的度数是连接到它的边的数量。

让每条边为黑色或白色。最初所有边缘都是黑色的。

为您提供了胡须图的描述。您的任务是分析以下类型的请求:

- 将编号 i 的边涂成黑色。边编号 i 是描述中具有该编号的边。保证在发出此请求时,第 i 条边是白色的
- 将编号 i 的边涂成白色。保证在发出此请求时,第 i 条边是黑色的
- 找到仅沿着顶点 a 和 b 之间的黑色边缘的最短路径的长度,或者表明它们之间不存在这样的路径(路径的长度是其中的边数)

顶点用 1 到 n 的整数编号,边用 1 到 n - 1 的整数编号。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 105) — 图中的顶点数。接下来的 n - 1 行包含边,描述为由该边连接的顶点数 vi, ui (1 ≤ vi, ui ≤ n, vi ≠ ui)。保证给定的图是连通的,形成胡须图,并且没有自环或重边。

下一行包含一个整数 m (1 ≤ m ≤ 3·105) — 请求数。接下来m行包含以下形式的请求:首先一行包含一个整数类型,取值从1到3,代表请求类型。

如果 type = 1,则当前请求是将边缘涂黑的请求。在这种情况下,除了数字类型之外,该行还应包含整数 id (1 ≤ id ≤ n - 1),它表示要绘制的边的编号。

如果type = 2,则当前请求为将边缘涂成白色的请求,其形式与之前的请求类似。

如果 type = 3,则当前请求是查找距离的请求。在这种情况下,除了类型之外,该行还应包含两个整数 a,b(1 ≤ a,b ≤ n,a 可以等于 b)——顶点的数量,必须找到顶点之间的距离。

所有行中的数字均以一个空格分隔。边按照输入中给出的顺序进行编号。

输出

对于每个“查找顶点 a 和 b 之间的距离”的请求,打印结果。如果没有仅沿着顶点 a 和 b 之间的黑色边缘延伸的路径,则打印“-1”(不带引号)。按照收到请求的顺序打印结果,用空格或换行符分隔数字。

示例

输入 #1

3
1 2
2 3
7
3 1 2
3 1 3
3 2 3
2 2
3 1 2
3 1 3
3 2 3

输出 #1

1
2
1
1
-1
-1

输入 #2

6
1 5
6 4
2 3
3 5
5 6
6
3 3 4
2 5
3 2 6
3 1 2
2 3
3 3 1

输出 #2

3
-1
3
2

注意

在第一个样本中,顶点 1 和 2 与边编号 1 连接,顶点 2 和 3 与边编号 2 连接。在重新绘制边编号 2 之前,每个顶点都可以沿着黑色边到达。具体来说,1 和 3 之间的最短路径沿着两条边。

如果我们将 2 号边涂成白色,顶点 3 最终将与其他顶点切断,也就是说,沿着黑色边不存在从它到任何其他顶点的路径。