烟花的寿命

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 firework.in 输出文件 firework.out
【问题描述

见过夜空中美丽的烟花吗,它们总是由一个块炸成多块,可能还会继续分裂成更小的块。然而,并不是每块都会继续发光。如果把一个烟花炸开的整个过程中的亮点记录下来,并给所有爆炸点标上号,你能算出它最长可能的存活时间吗?(指第一次爆炸到最后一次之间间隔的时问,假设任意两次相邻的爆炸时间间隔都是1秒)。
输入格式】
(输入文件名fireworlk.in)
第1行一个数T,说明输入文件中共T组数据。每组的第l行是爆炸的总数N(1
输出格式】
(输出文件名fireworlk.out)
对每组输入,输出若干行。第1行是最长的时间x(秒),接着输出x+1个数,每数占一行,给出最长时间是怎样达到的(从哪个点开始,经过哪些点)。如果存在多解,则任意输出一组解。
输入输出样例】
输入(firework.in)
2
3
1 2
1 3
4
1 2
2 4
3 2
输出(firework.out)
2
2
1
3
2
1
2
4
图为样例中第2组输出的示意图。