道路修建 Large
TimeLimit: 5000ms MemoryLimit:131072KB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description
无向图
初始有
个点，从
到依次标号，但是没有边，
接下来有
次操作，从到依次标号，你需要对每种操作输出相应的结果，操作分为两种：
| 输入格式 |
操作说明 |
输出结果 |
| 0_u_v |
加入一条连接标号为 |
输出加边后图 |
| 1_u_v |
查询标号为 |
如果连通，输出 |
，表示最早在第
。（输入格式中的下划线‘_’表示实际输入文件中的空格）
Input
第一行是一个正整数
，表示测试数据的组数，
对于每组测试数据，
第一行包含两个整数
、
，
接下来行，每行是
个整数
、
、
，请注意所给的、均是经过加密的，
解密方式是
、
，其中
表示上一次操作的输出结果，
初始
，保证
，解密后
且
。
Output
对于每组测试数据，
输出行，每行包含一个整数，表示操作的输出结果。
SampleInput
1 4 7 0 1 2 1 1 0 0 1 3 0 0 1 1 0 1 0 1 7 1 0 5
SampleOutput
3 0 2 2 3 1 6