你沉迷于最新的世界模拟游戏：Building A Perfect City。在当前的游戏进程中，你创建了一个街道数量与交叉路口数量相等的城市。现在剩下的工作就是给每条街道上的房屋编号。

该城市由一个包含交叉路口和街道的连通图表示。每条街道连接两个交叉路口 $u$ 和 $v$，并且有 $h$ 栋房屋，这些房屋都位于街道的一侧。任意两个交叉路口之间最多只有一条街道。

给这条街道上的房屋编号有两种方式：要么从靠近交叉路口 $u$ 的房屋编号为 1 开始，到靠近交叉路口 $v$ 的房屋编号为 $h$ 结束；要么从靠近交叉路口 $v$ 的房屋编号为 1 开始，到靠近交叉路口 $u$ 的房屋编号为 $h$ 结束。为了避免混淆，你需要确保没有任何一个交叉路口连接着两栋编号相同的房屋。

请找到一种为每条街道上的房屋编号的方法，使其满足上述性质（如果无法满足，请报告不可能）。

Numbers. Pixabay License

输入格式

输入包含：

• 第一行包含一个整数 $n$ ($3 \le n \le 10^5$)，表示交叉路口的数量，同时也表示街道的数量。
• 接下来 $n$ 行，每行包含三个整数 $u, v$ 和 $h$ ($u \neq v, 1 \le u, v \le n, 2 \le h \le 10^9$)，表示连接交叉路口 $u$ 和 $v$ 的一条街道，该街道上有 $h$ 栋房屋。

保证每个交叉路口都可以从其他任何交叉路口到达。任意两个交叉路口之间最多只有一条街道。

输出格式

如果无法实现，输出 “impossible”。否则，对于每条街道（按照输入的顺序），输出一个数字，表示房屋编号开始的交叉路口编号。

如果存在多个有效的解决方案，你可以输出其中任意一个。

样例

样例输入 1

3
1 2 2
2 3 9
3 1 3

样例输出 1

1
2
3

样例输入 2

4
1 2 2
1 3 2
2 3 2
1 4 2

样例输出 2

impossible