题目背景

你沉迷于一款城市模拟游戏，并建成了一座拥有相同数量街道和路口的城市。现在只差最后一步：为每条街道上的房屋编号。

题目描述

城市由一个连通无向图表示，共有 $n$ 个路口和 $n$ 条街道。

每条街道连接两个不同的路口 $u$ 和 $v$，街道的一侧共有 $h$ 栋房屋。对这条街道有两种编号方式：

• 从路口 $u$ 一端开始，靠近 $u$ 的房屋编号为 $1$，靠近 $v$ 的房屋编号为 $h$；
• 从路口 $v$ 一端开始，靠近 $v$ 的房屋编号为 $1$，靠近 $u$ 的房屋编号为 $h$。

为了避免混淆，你要求在任意一个路口处，所有与该路口相邻的房屋编号两两不同。

请为每条街道选择编号起点，使上述条件成立；若不存在合法方案，输出 impossible。

输入格式

第一行包含一个整数 $n$，表示路口数量，同时也表示街道数量。

接下来 $n$ 行，每行包含三个整数 $u,v,h$，表示一条连接路口 $u$ 和 $v$ 的街道，街道上共有 $h$ 栋房屋。

题目保证：

• 整张图连通；
• 任意两个路口之间至多有一条街道。

输出格式

若不存在合法方案，输出：

impossible

否则，按照输入顺序，对每条街道输出一行，内容为该街道编号开始一端的路口编号。

若有多种合法方案，可以输出任意一种。

数据范围

样例 1

输入

3
1 2 2
2 3 9
3 1 3

输出

1
2
3

样例 2

输入

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

输出

impossible