No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: 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 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.

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

For each vertex of synchrograph detect whether it is alive.

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

For each vertex print 1 if it is alive and 0 in the other case.

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

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

0

0

0

0

1

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: | 2003-06-26 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2019 20:01:46 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|