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$$。