#P6909. light

    ID: 6740 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-二分答案广度优先搜索无向连通分量路径恢复DMP 平面性判定

light

题目描述

最初有一张长方形纸,上、右、下、左四条边的编号依次为 1,2,3,41,2,3,4。

给出 nn 次切割操作。第 ii 次操作选择一张同时具有编号 aia_i 和 bib_i 两条边的纸,沿这两条边中点的连线将它剪成两张。切割后,原有边及其被切开的各段都保留原编号,两张纸上新产生的切边均编号为 i+4i+4。若有多张纸可选,可以任选一张。

求最多能按顺序完成前多少次操作。无法完成某一步时,不能跳过该步继续。

输入格式

第一行一个正整数 TT,表示测试组数。

对于每组数据,第一行一个正整数 nn,接下来 nn 行,每行两个正整数 ai,bia_i,b_i。

输出格式

对每组数据输出一行一个整数,表示最多能按顺序完成的操作数。

样例

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≤T≤51\le T\le5,1≤n≤2001\le n\le200,1≤ai,bi≤i+31\le a_i,b_i\le i+3,ai≠bia_i\ne b_i。任意两次操作的无序边编号对均不同。

原题子任务 额外限制 分值
1 n≤10n\le10 10
2 n≤40n\le40 40
3 无 50

By sunset

原 PDF 题面