克罗地亚一家化学实验室的科学家们一直在研究不同分子之间的化学键。他们对化学化合物硝基氢层压板（nitro hydrogen laminate）中的一组分子特别感兴趣。

该化合物由 $N$ 个分子组成，它们通过 $N - 1$ 个共价键连接在一起，所有分子都直接或间接地通过化学键连接在一个单一结构中。

科学家们希望对该化合物进行改造，使得所有的共价键都转化为有向共价键。由于新生成的化合物具有不稳定性，每个分子都会产生大量的脉冲，这些脉冲会沿着有向键传播到其他分子。脉冲只能沿着有向共价键的方向进行传播。

该化合物的不稳定性定义为单个脉冲在传播过程中最多可以经过的化学键数量。科学家们希望为该化合物的共价键定向，使得新生成的化合物尽可能稳定。换句话说，他们的目标是使脉冲在传播过程中所能经过的最长路径尽可能短。

请帮助科学家们确定化合物中每个共价键的方向。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 100\,000$)。

接下来的 $N - 1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le N$)，表示分子 $a_i$ 和 $b_i$ 之间连接着一个共价键。

输出格式

输出 $N - 1$ 行，每行包含一个整数。如果第 $i$ 个共价键的方向是从 $a_i$ 指向 $b_i$，则输出 1；否则输出 0。

如果有多种可能的解，输出任意一种即可。

子任务

对于至少 30% 的测试数据，满足 $N \le 20$。

样例

输入样例 1

3
1 2
2 3

输出样例 1

1
0

输入样例 2

4
2 1
1 3
4 1

输出样例 2

0
1
0

说明

样例 1 说明：该样例对应题目描述中左侧的图。脉冲可以经过的最长路径长度为 1。注意，0 1 也是一个正确的解。

样例 2 说明：该样例对应题目描述中右侧的图。