#P6909. light
light
题目描述
最初有一张长方形纸,上、右、下、左四条边的编号依次为 。
给出 次切割操作。第 次操作选择一张同时具有编号 和 两条边的纸,沿这两条边中点的连线将它剪成两张。切割后,原有边及其被切开的各段都保留原编号,两张纸上新产生的切边均编号为 。若有多张纸可选,可以任选一张。
求最多能按顺序完成前多少次操作。无法完成某一步时,不能跳过该步继续。
输入格式
第一行一个正整数 ,表示测试组数。
对于每组数据,第一行一个正整数 ,接下来 行,每行两个正整数 。
输出格式
对每组数据输出一行一个整数,表示最多能按顺序完成的操作数。
样例
2
4
3 1
1 5
4 6
2 4
5
3 4
1 2
5 6
1 5
8 7
3
5
第一组数据中,第一刀把长方形分成左右两块。第二刀若选右边那块,第三刀便无法完成。若选左边那块,第三刀可继续,第四刀无法完成。切割示意图见原 PDF。
数据范围
对于全部数据,,,,。任意两次操作的无序边编号对均不同。
| 原题子任务 | 额外限制 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2 | 40 | |
| 3 | 无 | 50 |
By sunset