OI题库

【问题描述】

见过夜空中美丽的烟花吗，它们总是由一个块炸成多块，可能还会继续分裂成更小的块。然而，并不是每块都会继续发光。如果把一个烟花炸开的整个过程中的亮点记录下来，并给所有爆炸点标上号，你能算出它最长可能的存活时间吗?(指第一次爆炸到最后一次之间间隔的时问，假设任意两次相邻的爆炸时间间隔都是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组输出的示意图。