题目描述

Miranda 生活的城市有 $N$ 个小镇，一开始小镇间没有任何道路连接。随着经济发展，小镇之间陆续建起了一些双向的道路。由于经济不太发达，在建设过程中，会保证对于任意两个小镇，最多有一条路径能互相到达。

有时候 Miranda 会从某个小镇开始进行徒步旅行。每次出发前，她都想选择一个她能到达的最远的小镇作为终点，并且她在行走过程中是不会走回头路的。为了估算这次旅行的时间，她会需要你告诉她这次旅行的时间会是多少呢？可以假设通过每条道路都需要单位时间，并且 Miranda 不会在小镇停留。

输入格式

• 第一行一个整数 $\text{type}$，表示数据类型。
• 第二行两个整数 $N$、$Q$。
• 接下来 $Q$ 行，每行先读入一个整数 $t$：
  • 若 $t = 1$，则接下来读入两个整数 $u$、$v$，表示小镇 $u$ 与小镇 $v$ 建立了一条新道路。
  • 若 $t = 2$，读入一个整数 $u$，表示 Miranda 要开始一次从小镇 $u$ 出发的旅行。

特殊处理：

• 若 $\text{type} = 1$，记 $\text{lastAns}$ 表示最近一次 Miranda 旅行的时间，那么对于每次操作的 $u$ 或 $u, v$，都要异或上 $\text{lastAns}$。
• 若 $\text{type} = 0$，则不需要对数据进行处理。

输出格式

对于每次询问，输出 Miranda 能到达的最远的小镇的距离是多少。注意 Miranda 可能只能留在开始的小镇。

样例

输入

0
5 10
1 4 5
2 3
2 5
2 1
1 5 3
1 1 4
2 3
2 5
1 5 2
2 1

输出

0
1
0
3
2
3

数据范围与提示

• 对于 $20\%$ 的数据，$N \leq 5000, Q \leq 10000$；
• 对于 $50\%$ 的数据，$N \leq 100000, Q \leq 200000$；
• 对于另外 $20\%$ 的数据，$\text{type} = 0$；
• 对于 $100\%$ 的数据，$N \leq 300000, Q \leq 500000, \text{type} \in \{ 0, 1 \}$，解密后的 $u$、$v$ 满足 $1 \leq u, v \leq N$，且道路的修建会满足：每一时刻，都不存在 $u, v$ 使得 $u, v$ 之间能通过多种方式到达。