CF269C.Flawed Flow

Emuskald considers himself a master of flow algorithms. Now he has completed his most ingenious program yet — it calculates the maximum flow in an undirected graph. The graph consists of n vertices and m edges. Vertices are numbered from 1 to n. Vertices 1 and n being the source and the sink respectively.

However, his max-flow algorithm seems to have a little flaw — it only finds the flow volume for each edge, but not its direction. Help him find for each edge the direction of the flow through this edges. Note, that the resulting flow should be correct maximum flow.

More formally. You are given an undirected graph. For each it's undirected edge (a__i, b__i) you are given the flow volume c__i. You should direct all edges in such way that the following conditions hold:

1. for each vertex v (1 < v < n), sum of c__i of incoming edges is equal to the sum of c__i of outcoming edges;
2. vertex with number 1 has no incoming edges;
3. the obtained directed graph does not have cycles.

Emuskald 认为自己是一位网络流算法大师。如今，他完成了迄今为止最精巧的程序——该程序用于计算无向图中的最大流。该图包含 $n$ 个顶点和 $m$ 条边，顶点编号为 $1$ 到 $n$，其中顶点 $1$ 和顶点 $n$ 分别为源点（source）和汇点（sink）。

然而，他的最大流算法似乎存在一个小缺陷——它仅能计算出每条边上的流量值，却无法确定流的方向。请帮助他为每条边确定其上的流方向。注意：最终得到的流必须是一个正确的最大流。

更形式化地描述如下：你被给定一个无向图。对于每条无向边 $(a_i, b_i)$，你已知其流量值 $c_i$。你需要为所有边指定方向，使得满足以下条件：

1. 对每个顶点 $v$（其中 $1 < v < n$），所有指向 $v$ 的边的流量值 $c_i$ 之和，等于所有从 $v$ 出发的边的流量值 $c_i$ 之和；
2. 编号为 $1$ 的顶点没有入边；
3. 所得的有向图中不存在环。

The first line of input contains two space-separated integers n and m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105), the number of vertices and edges in the graph. The following m lines contain three space-separated integers a__i, b__i and c__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ c__i ≤ 104), which means that there is an undirected edge from a__i to b__i with flow volume c__i.

It is guaranteed that there are no two edges connecting the same vertices; the given graph is connected; a solution always exists.

输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$（$2 \leq n \leq 2\cdot10^5$，$n-1 \leq m \leq 2\cdot10^5$），分别表示图中的顶点数和边数。接下来的 $m$ 行每行包含三个用空格分隔的整数 $a_i$、$b_i$ 和 $c_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq c_i \leq 10^4$），表示存在一条连接顶点 $a_i$ 与 $b_i$ 的无向边，其流量容量为 $c_i$。

保证不存在连接相同两个顶点的两条边；给定图是连通的；且解一定存在。

Output m lines, each containing one integer d__i, which should be 0 if the direction of the i-th edge is a__i → b__i (the flow goes from vertex a__i to vertex b__i) and should be 1 otherwise. The edges are numbered from 1 to m in the order they are given in the input.

If there are several solutions you can print any of them.

输出 $m$ 行，每行包含一个整数 $d_i$：若第 $i$ 条边的方向为 $a_i \to b_i$（即流从顶点 $a_i$ 流向顶点 $b_i$），则 $d_i$ 应为 $0$；否则（即方向为 $b_i \to a_i$）应为 $1$。边按输入中给出的顺序编号，从 $1$ 到 $m$。

若存在多个解，输出任意一个即可。

In the first test case, 10 flow units pass through path , and 5 flow units pass directly from source to sink: .

在第一个测试用例中，有 10 个流量单位经过路径 ，另有 5 个流量单位直接从源点流向汇点：。