菱形衣架的排列¶
- 参考时间限制：0.5 秒（参考环境：R30；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB
背景故事¶
你买了一组菱形衣架。衣架可以挂在另一个衣架的下端或右端，最终连成一体。请按图中从上到下、每行从左到右的顺序列出编号。
形式化问题描述¶
衣架编号为 \(1,\ldots,n\) .衣架 \(i\) 的下方和右方孩子分别为 \(d_i,r_i\) ；零表示没有该孩子。所有非零连接组成一棵有根树，且每个衣架至多各有一个下方孩子和右方孩子。根由输入唯一确定。
根所在行的层数为零。下方连接使层数增加一、中心横坐标不变；右方连接保持层数不变。层数 \(h\) 越小，位置越高。
为明确左右顺序，令 \(B=2n+1\) ，同层衣架的水平半对角线长度均为 \(B^{-h}\) .根的中心横坐标为零；右方孩子的中心横坐标比父亲大 \(2B^{-h}\) .衣架的竖直对角线等长，下方连接恰好下降一层。该尺度使高处衣架远宽于低处衣架。无需计算或输出这些坐标，只需输出每个非空层内从左到右的编号。
输入格式¶
第一行一个整数 \(n\) .接下来 \(n\) 行，第 \(i\) 行是 \(d_i,r_i\) .
输出格式¶
按层数递增输出，每个非空层一行；同一行按横坐标递增列出衣架编号，以空格分隔。每个编号恰好输出一次。
样例 1¶
输入¶
6
2 3
4 5
6 0
0 0
0 0
0 0
输出¶
1 3
2 5 6
4
解释¶
最高层是衣架一、三；第二层是二、五、六；第三层只有四。
图中压缩了各层宽度差异以便阅读，连接关系及各行编号顺序与题意一致。
样例 2¶
输入¶
1
0 0
输出¶
1
解释¶
只有一个衣架。
样例 3¶
输入¶
3
0 0
0 1
0 2
输出¶
3 2 1
解释¶
根是三号，三个衣架沿右方连接，处于同一层。
数据范围与保证¶
\(1\le n\le10^5\) ，\(0\le d_i,r_i\le n\) .所有连接保证满足上述有根树条件。
数据规格由 Codex（GPT-6）补齐：确定规模、合法树保证、同层尺寸与层间比例，并明确输出衣架编号。
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 20% | \(n\le20\) |
| 30% | \(n\le1000\) |
| 50% | 无额外条件 |