7609: 部落冲突

超级细胞王国住着 $n$ 个野蛮人，一开始第 $i$ 个人各自在部落 $i$。为了共同抵御哥布林的入侵，野蛮人会在部落之间游走，进行结盟，交换，移动等操作。 作为哥布林派来的间谍，你观察到了每个野蛮人的去向，但是想知道某个野蛮人在哪个部落仍然是一件困难的事情。所以他来寻求你的帮助，希望你写一个程序帮帮他！ 总共有 $q$ 个操作，操作类型包括： - $1\ a\ b$：$a$ 部落与 $b$ 部落结盟。结盟操作使部落合并，新部落的编号是 $a$ 部落的编号； - $2\ a\ b$：野蛮人 $a$ 移动到部落 $b$ 中； - $3\ a\ b$：$a$ 部落中的所有野蛮人转移到 $b$ 部落，$b$ 部落的野蛮人同时转移到 $a$ 部落中； - $4\ a$：查询 $a$ 野蛮人所在部落的编号。 --- 为了防止输入过大带来的常数问题，`C++` 选手请尽量使用关闭流同步的 `std::cin` 和 `std::cout` 实现输入输出，否则可能出现因读入输出问题导致的 TLE 等。 ```cpp int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); // your code return 0; } ```

第一行一个整数 $ T $ $ \left(1 \leq T \leq 6\right) $，表示测试数据组数。 对于每组数据，第一行包含两个用空格分隔的正整数 $ n , q $ $ \left(1\leq n,q \leq 10^6\right)$。 接下来 $q$ 行，每一行按如下格式给出一个操作： - $1\ a\ b$：$a$ 部落与 $b$ 部落结盟。结盟操作使部落合并，新部落的编号是 $a$ 部落的编号； - $2\ a\ b$：野蛮人 $a$ 移动到部落 $b$ 中； - $3\ a\ b$：$a$ 部落中的所有野蛮人转移到 $b$ 部落，$b$ 部落的野蛮人同时转移到 $a$ 部落中； - $4\ a$：查询 $a$ 野蛮人所在部落的编号。 保证操作中出现的部落一定合法。

对于所有操作 $4$，输出 $a$ 野蛮人所在部落的编号。