219. Synchrograph
time limit per test: 0.25
sec.
memory limit per test: 65536
KB
input: standard
output: standard
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 nonnegative 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.
Input
The first line of the input file 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 10^{9}.
Output
For each vertex print 1 if it is alive and 0 in the other case.
Sample test(s)
Input
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
Output
1
0
0
0
0
1
Note
11.12.2003. Clarification done: "For each vertex of synchrograph detect whether it is potentially alive" changed to "For each vertex of synchrograph detect whether it is alive".
Author:  Andrew Stankevich

Resource:  Summer Trainings 2003, Maloyaroslavets

Date:  20030626

Server time: 20180222 00:18:41  Online Contester Team © 2002  2016. All rights reserved. 

