← 返回题目列表

Codeforces · 269/C

C. 有缺陷的流程

中文机器翻译题面 查看原题

Emuskald 认为自己是流算法大师。现在他已经完成了迄今为止最巧妙的程序——它计算无向图中的最大流。该图由 n 个顶点和 m 个边组成。顶点编号为 1 到 n。顶点 1 和 n 分别是源点和汇点。

然而,他的最大流量算法似乎有一点缺陷——它只找到每条边的流量,而不是它的方向。帮助他找到每条边的流过该边的方向。请注意,所得流量应该是正确的最大流量。

更正式。给你一个无向图。对于每个无向边 (ai, bi),您都会得到流量 ci。您应以满足以下条件的方式引导所有边:

1.对于每个顶点v(1 < v < n),入边ci之和等于出边ci之和;
2. 编号为1的顶点没有入边;
3.得到的有向图没有环。

输入

输入的第一行包含两个空格分隔的整数 n 和 m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105),即图中的顶点数和边数。接下来的 m 行包含三个空格分隔的整数 ai、bi 和 ci(1 ≤ ai,bi ≤ n,ai ≠ bi,1 ≤ ci ≤ 104),这意味着从 ai 到 bi 存在一条无向边,流量为 ci。

保证没有两条边连接相同的顶点;给定的图是连通的;解决方案总是存在的。

输出

输出 m 行,每行包含一个整数 di,如果第 i 条边的方向为 ai → bi(流从顶点 ai 到顶点 bi),则应为 0,否则应为 1。边按照输入中给出的顺序从 1 到 m 进行编号。

如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

3 3
3 2 10
1 2 10
3 1 5

输出 #1

1
0
1

输入 #2

4 5
1 2 10
1 3 10
2 3 5
4 2 15
3 4 5

输出 #2

0
0
1
1
0

注意

在第一个测试用例中,10 个流单元通过路径 $$1 \rightarrow 2 \rightarrow 3$$,5 个流单元直接从源到接收器:$$\rightarrow$$。