UOJ Logo Universal Online Judge

UOJ

#134. 【UR #9】App 管理器

统计

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 \geq 1, m \geq 0$。

接下来 $m$ 行,每行三个整数 $a_i, b_i, t_i$,表示一个 App。如果 $t_i = 0$ 则表示这个 App 还没被卸载一半,如果 $t_i = 1$ 则表示这个 App 已经被卸载一半,现在只能把 $a_i$ 号格式转换为 $b_i$ 号格式。保证 $1 \leq a_i, b_i \leq n$ 且 $a_i \neq 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

样例二

见样例数据下载。

限制与约定

测试点编号$n, m$ 的规模特殊限制
1$n, m \leq 17$
2
3
4$n, m \leq 5000$所有 $t_i = 0$
5
6
7
8
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载