# 菱形衣架的排列

- 参考时间限制：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

### 输入

```text
6
2 3
4 5
6 0
0 0
0 0
0 0
```

### 输出

```text
1 3
2 5 6
4
```

### 解释

最高层是衣架一、三；第二层是二、五、六；第三层只有四。

![图中压缩了各层宽度差异以便阅读，连接关系及各行编号顺序与题意一致。](assets/example.svg)

图中压缩了各层宽度差异以便阅读，连接关系及各行编号顺序与题意一致。

## 样例 2

### 输入

```text
1
0 0
```

### 输出

```text
1
```

### 解释

只有一个衣架。

## 样例 3

### 输入

```text
3
0 0
0 1
0 2
```

### 输出

```text
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% | 无额外条件 |

[参考评测环境与测量](../../../docs/评测环境与性能.md)