题目描述

有 $N$ 个点和 $N-1$ 条无向边，定义一张有向图的代价为一条在这张有向图上的最长通路长度。

现在把这 $N-1$ 条无向边指定方向，使得形成的有向图代价最小。

求一种指定方向的方案。

为了让本题能使用标准输出比较器评测，GESPOJ 规定采用下面这组唯一的最优方案：以结点 $1$ 为根，根的深度为 $0$；将每条边都从偶数深度的端点指向奇数深度的端点。树是二分图，因此该规则总能确定每条边的方向，且得到的最长有向路径长度为 $1$，一定最优。

输入格式

第一行一个整数 $N$ 代表点数。
接下来 $N-1$ 行每行两个整数 $a_i,b_i$ 代表一条边。

输出格式

$N-1$ 行每行一个整数 $r$：

• 如果 $r=1$ 代表从 $a_i$ 连向 $b_i$。
• 如果 $r=0$ 代表从 $b_i$ 连向 $a_i$。

输出必须遵守题目描述中的 GESPOJ 固定规则。

输入输出样例

3
1 2
2 3

1
0

4
2 1
1 3
4 1

0
1
0

说明/提示

样例 1 解释

如下图所示：

这张图的代价为 $1$，注意 $0\ 1$ 也是一组最优解。

样例 2 解释

如下图所示：

数据规模与约定

对于 $30\%$ 的数据，$N \le 20$。
对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le a_i,b_i\le N$。

洛谷原题采用 Special Judge、允许任意最优方案；GESPOJ 为保证本地标准评测稳定，采用上文规定的固定最优方案。

说明

翻译自 COCI 2015-2016 #3 C MOLEKULE。

5
1 2
3 2
4 1
5 4

1
1
0
1