让我们定义一个由 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 最终将与其他顶点切断,也就是说,沿着黑色边不存在从它到任何其他顶点的路径。