#CF2004B. 门与游戏
门与游戏
B. 门与游戏
时间限制:每测试点 秒
内存限制: 兆字节
有 个房间排成一排,它们之间有 道门;第 道门连接房间 和 。每道门可以是锁上的或者未锁的。初始时,所有门都是未锁的。
我们称房间 可以从房间 到达,如果它们之间所有的门都是未锁的。
已知:
- 爱丽丝位于区间 中的某个房间;
- 鲍勃位于区间 中的某个房间;
- 爱丽丝和鲍勃在不同的房间。
但你不知道他们具体在哪个房间。
你不想让爱丽丝和鲍勃能够互相到达,因此你准备锁上一些门来阻止这种情况。问:最少需要锁上多少道门,使得无论他们在给定区间内的起始位置如何,爱丽丝和鲍勃都无法相遇?
输入格式
第一行包含一个整数 ()——测试用例的数量。
每个测试用例的第一行包含两个整数 和 ()——爱丽丝所在房间的区间范围。
每个测试用例的第二行包含两个整数 和 ()——鲍勃所在房间的区间范围。
输出格式
对于每个测试用例,输出一个整数——最少需要锁上的门数量,使得无论他们在给定区间内的起始位置如何,他们都不能相遇。
样例输入
4
1 2
3 4
2 5
2 5
3 7
6 7
4 5
2 8
样例输出
1
3
2
3
样例解释
- 第一个测试用例:只需锁上房间 和 之间的门。
- 第二个测试用例:必须锁上门 、、。
- 第三个测试用例:必须锁上门 和 。