华师一附中OI组

标题: 破坏公路 [打印本页]

作者: admin 时间: 2018-5-13 00:53
标题: 破坏公路
题目描述：

在太平洋中心有一个圆形小岛，沿着小岛的海岸线分布着n个小镇，编号分别为1,2,3~~n；小镇i-1、小镇i、小镇i+1是相邻的（当然小镇n与小镇1相邻）。相邻小镇之间存在一条公路，公路也有编号，公路i连接小镇i和小镇i+1，公路n连接小镇n和小镇1.现在对小岛有m个操作，操作有两种：
询问操作：1 x y 代表小镇x到小镇y是否联通，联通输出1，否则输出0
修改操作：0 x 代表修改公路x，如果公路原来是完好的，则断开，否则修好公路x。
输入格式:
输入第一行为一个整数t，代表下来有t组数据
每组数据输入第一行包含两个整数n，m，分别表示小镇个数和操作命令数目。
输入接下来的m行，每一行代表一条操作指令。
输出格式:
对于相邻两组数据之间要留一空行。
输入样例：
1
5 10
1 2 5
0 4
1 4 5
0 2
1 3 4
1 1 3
0 1
0 2
1 2 4
1 2 5
输出样例：
1
1
1
0
1
0
数据规模:
对于20%的数据满足：1 < = n, m <=1000。
对于40%的数据满足：1 < = n, m <= 100000。
对于100%的数据满足：1 < = n, m <= 500000。

欢迎光临华师一附中OI组 (http://hsyit.cn/)