样例下载

题目背景

B 地区在地震过后，所有公路都造成了一定的损毁，而这场地震却没对村庄造成什么影响。当地部门正在对公路进行重建。

题目描述

B 地区共有 $N$ 个村庄，编号从 $1$ 到 $N$。有若干条双向通行的公路需要重建。每条公路都连接两个不同的村庄（无自环），两个不同的村庄之间可能有多条公路（可能有重边）。

现在，小 A 作为重建公路的负责人，接到了上级部门发来的 M 个命令，他需要依次执行。

命令分为两种类型：

• 修建命令：形如 0 i j ，小 A 需要立刻组织工人重建从村庄 i 到 j 之间的公路;
• 回复命令：形如 1 i j ，小 A 需要回复上级部门，村庄 i 和 j 最早是在重建完第几条公路后连通的。如果当前仍未连通，则回复 0

你能帮助小 A 吗？

输入格式

第一行包含两个整数 $N, M$，依次表示村庄的数目、命令的数目。

接下来 $M$ 行，按顺序依次给出了每个命令：每行 $3$ 个整数 k i j，其中 k 只可能为 0 或 1，含义如题目所述。

注：本题强制在线，假设上一个回复命令的答案为 lastans，则对于所有命令的 i 和 j，其执行的真正值应该是读入的 i, j 分别异或 lastans。初始时 lastans = 0

输出格式

对于每个回复命令，输出小 A 回复的答案，每个回复答案占一行。

样例输入

5 9
0 1 4
1 2 5
0 2 4
0 3 4
1 3 1
0 7 0
0 6 1
0 1 6
1 2 6

样例输出

0
3
5

数据范围

100% 的数据： $1 ≤ N, M ≤ 5 × 10^5$， 数据保证真正执行的 i, j 满足 $1 ≤ i, j ≤ N$ 且 $i ≠ j$