← 返回题目列表

Codeforces · 938/G

G. 最短路径查询

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

给您一个带有加权边的无向连通图。两个顶点之间的某个路径的长度是属于该路径的所有边的权重的按位异或(如果某条边被遍历多次,则它被包含在按位异或相同的次数中)。

您必须处理三种类型的查询:

- 1 x y d — 添加一条边,将顶点 x 连接到顶点 y,权重为 d。保证在本次查询之前不存在连接x到y的边;
- 2 x y — 删除连接顶点 x 和顶点 y 的边。保证图中存在这条边,并且在本次查询后图仍保持连通;
- 3 x y — 计算从顶点 x 到顶点 y 的最短路径(可能不简单)的长度。

打印类型 3 的所有查询的答案。

输入

第一行包含两个数字 n 和 m (1 ≤ n, m ≤ 200000) — 分别是图中的顶点数和边数。

接下来的 m 条线表示图形的边缘。每行包含三个整数 x、y 和 d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1)。每对 (x, y) 最多列出一次。初始图已连接。

接下来一行,包含一个整数 q (1 ≤ q ≤ 200000) — 您必须处理的查询数。

接下来是 q 行,表示以下形式的查询:

- 1 x y d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1) — 添加一条边,将顶点 x 连接到权重为 d 的顶点 y。保证在本次查询之前不存在连接x到y的边;
- 2 x y (1 ≤ x < y ≤ n) — 删除连接顶点 x 和顶点 y 的边。保证图中存在这条边,并且在本次查询后图仍保持连通;
- 3 x y (1 ≤ x < y ≤ n) — 计算从顶点 x 到顶点 y 的最短路径(可能不是简单路径)的长度。

保证至少一个查询具有类型 3。

输出

按照输入中出现的顺序打印类型 3 的所有查询的答案。

示例

输入 #1

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

输出 #1

1
1
2