iOS 用户和 Android 用户一定对 App 管理器不会陌生。

“啊啊啊！手机空间又不够了” 买了低端机的奸笑熊欲哭无泪。

奸笑熊常有的文件格式一共有 $n$ 种，分别编号为 $1,\dots ,n$。奸笑熊有 $m$ 个 App，分别编号为 $1,\dots ,m$。其中 $i$ 号 App 可以把 $a_i$ 号文件格式转换成 $b_i$ 号文件格式，或者把 $b_i$ 号文件格式转换成 $a_i$ 号文件格式。

App 管理器最近推出了一个新功能：卸载一半！于是奸笑熊决定把每个 App 都卸载一半。

对于 $i$ 号 App，你可以决定你卸载哪一半：

1. 把 $a_i$ 号文件格式转换成 $b_i$ 号文件格式。
2. 把 $b_i$ 号文件格式转换成 $a_i$ 号文件格式。

奸笑熊希望，把所有 App 都卸载一半之后并不影响使用。即，对于任意两个文件格式 $i,j$，仍能通过一个或多个 App 把 $i$ 号文件格式直接或间接转换成 $j$ 号文件格式。

现在奸笑熊已经把部分 App 卸载一半了，请你给出一组卸载剩下的 App 的方案满足条件。

输入格式

第一行两个整数 $n,m$，表示文件格式的数量和 App 的数量。保证 $n\ge 1,m\ge 0$。

接下来 $m$ 行，每行三个整数 $a_i,b_i,t_i$，表示一个 App。如果 $t_i=0$ 则表示这个 App 还没被卸载一半，如果 $t_i=1$ 则表示这个 App 已经被卸载一半，现在只能把 $a_i$ 号格式转换为 $b_i$ 号格式。保证 $1\le a_i,b_i\le n$ 且 $a_i\ne b_i$。

输出格式

输出 $m$ 行，每行一个整数表示卸载的是哪一半。

如果这个 App 还没被卸载一半，输出 $0$ 表示保留 “把 $a_i$ 号文件格式转换成 $b_i$ 号文件格式” 的这一半，否则表示保留 “把 $b_i$ 号文件格式转换成 $a_i$ 号文件格式” 的这一半。

如果这个 App 已经被卸载一半，那么直接输出 $0$。

保证至少存在一组方案。

样例一

input

4 5
1 2 0
2 3 0
1 3 1
4 1 1
4 3 0

output

0
0
0
0
1

样例二

见样例数据下载。

限制与约定

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载