MianKing 有一个图构造器：它的输入是一个序列 $a_{1 \dots n}$（$0 \le a_i < 2^{60}$），输出是一个包含 $n$ 个节点的无向图，当且仅当 $(a_x \text{ or } a_y) = 2^{60} - 1$ 时，图中存在边 $(x, y)$。

例如，如果输入为 $a_{1 \dots 3} = \{2^{60} - 1, 2^{60} - 2, 1\}$，则输出的图为 $\{(1, 1), (1, 2), (1, 3), (2, 3)\}$。

现在 GreenKing 有一棵包含 $n$ 个节点的树，MianKing 想要找到一个序列作为输入来构造出这棵树。你需要帮助他找到一个满足条件的序列。

第一行包含一个整数 $n$。 接下来有 $n - 1$ 行，每行包含两个整数 $(x, y)$，表示树中的一条边。 $1 \le n \le 100$。

输出 $n$ 个整数 $a_{1 \dots n}$，表示你找到的序列。 你需要保证 $0 \le a_i < 2^{60}$。 题目保证解一定存在。

样例

输入格式 1

3
1 2
2 3

输出格式 1

1 1152921504606846974 1