[ABC350] G - Mediator

G - Mediator

Time Limit: 3 sec / Memory Limit: 256 MB

分数: 600 分

题面

注意特殊的输入格式和比通常更小的内存限制。

有一个无向图，顶点为 ，初始时没有边。
需要在该图上处理以下 个查询：

1

类型 : 在顶点 和 之间添加一条边。
在添加边之前， 和 属于不同的连通分量（即图始终保持森林的结构）。

2

类型 : 如果存在一个顶点既与 相邻又与 相邻，则报告这个顶点的编号；否则报告 。
鉴于图始终保持森林的结构，此查询的答案是唯一确定的。

这些查询以加密形式给出。
原始查询由三个整数 定义，加密查询由三个整数 给出。
设 为第 个类型为 的查询的答案。定义当 时 。
按照以下方式从给定的 恢复 ：

• 令 为此查询之前给出的类型为 的查询数量（不包括查询本身）。然后使用以下公式：

限制条件

• 所有输入值均为整数。

---

输入

输入以以下格式从标准输入给出:

输出

设 为类型为 的查询数量。输出 行。
第 行应包含第 个类型为 的查询的答案。

---

样例输入 1

6 12
143209915 123840720 97293110
89822758 207184717 689046893
67757230 270920641 26993265
952858464 221010240 871605818
730183361 147726243 445163345
963432357 295317852 195433903
120904472 106195318 615645575
817920568 27584394 770578609
38727673 250957656 506822697
139174867 566158852 412971999
205467538 606353836 855642999
159292205 319166257 51234344

样例输出 1

0
2
0
2
6
0
1

解密所有查询后，输入如下：

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

这个输入有一个 个顶点的图和 个查询。

• 第一个查询是 2 1 3。
  • 没有顶点既与顶点 又与顶点 相邻，因此报告 。
• 第二个查询是 1 2 6。
  • 在顶点 和顶点 之间添加一条边。
• 第三个查询是 1 2 4。
  • 在顶点 和顶点 之间添加一条边。
• 第四个查询是 1 1 3。
  • 在顶点 和顶点 之间添加一条边。
• 第五个查询是 2 4 6。
  • 既与顶点 又与顶点 相邻的顶点是顶点 。
• 第六个查询是 2 1 4。
  • 没有顶点既与顶点 又与顶点 相邻，因此报告 。
• 第七个查询是 1 5 6。
  • 在顶点 和顶点 之间添加一条边。
• 第八个查询是 1 1 2。
  • 在顶点 和顶点 之间添加一条边。
• 第九个查询是 2 1 4。
  • 既与顶点 又与顶点 相邻的顶点是顶点 。
• 第十个查询是 2 2 5。
  • 既与顶点 又与顶点 相邻的顶点是顶点 。
• 第十一个查询是 2 3 4。
  • 没有顶点既与顶点 又与顶点 相邻，因此报告 。
• 第十二个查询是 2 2 3。
  • 既与顶点 又与顶点 相邻的顶点是顶点 。

---

样例输入 2

2 1
377373366 41280240 33617925

样例输出 2

可以为空。