In the theory of processes a special case of Petri nets is often considered, called synchrographs. Synchrograph can be represented as directed graph, each arc of which is marked with some non-negative integer number. The vertex of synchrograph is called active if all arcs incoming into this vertex are marked with the positive number.
Synchrograph operates in cycles. Each cycle one active vertex is nondeterministically selected and fired. The vertex fires the following way: the number on each arc incoming into this vertex is decreased by one, and the number on each arc outgoing from this vertex is increased by one. After that the set of active vertices is refreshed due to the new marks of the arcs and the next cycle takes place.
The vertex of synchrograph is called potentially alive if there is the sequence of fires, such that after it the vertex itself fires. The vertex is called alive if after any valid sequence of fires it is potentially alive.
For each vertex of synchrograph detect whether it is alive.
There may be multiple inputs, terminated by EOF.
The first line of the each testcase contains N and M — the number of vertices and arcs of synchrograph respectively (1 ≤ N ≤ 1000, 1 ≤ M ≤ 50000). Next M lines contain arc descriptions --- the beginning of the arc, the end of the arc and the number that this arc is initially marked with. No mark exceeds 109.
For testcase print N lines. Print for each vertex 1 if it is alive and 0 in the other case.
6 8 1 2 1 4 3 0 2 4 0 4 3 1 1 6 0 6 3 1 3 2 0 4 5 1000000000
1 0 0 0 0 1
Migrated from old NTUJ.
sgu219
| No. | Testdata Range | Score |
|---|