A Walk to Remember

4

162 votes
Approved, Graphs, Medium, Ready
Problem

Dilku was thinking about the first time he met his girl... It was indeed a walk to remember. The romantic weather and her silly talks. He was completely mesmarized. Those were the days!..

Today is his girl's birthday and he wants to make it special for her. He wants to again take her on a "special walk" that they would remember for the lifetime.

The city in which Dilku lives is represented as an unweighted directed graph with N nodes and M edges. A "special walk" in the graph starting at node u is a simple path that begins and ends at the same node u.

Formally, A special walk is path u , a1 , a2 , a3 ,..., ai ,.... , u where ai are distinct and not equal to u for all i.

Now since Dilku is really nervous about taking his girl out, he needs your help. For every node in the given graph, tell whether it is possible for Dilku to take his girl on a "special walk" starting at that node.

Input:

First line of a two space separated integers denoting N and M, the number of nodes and number of directed edges in the corresponding graph.
Following M lines contain two space separated integers u v denoting a directed edge in the graph from vertex numbered u to vertex numbered v.

Output:

Print N space separated integers, where ith integer can be either 1 or 0 depicting whether it is possible to go on a special walk starting at node i or not.

Constraints:

  • 1 ≤ N ≤ 105
  • 1 ≤ M ≤ 2 · 105
  • 1 ≤ u, vN
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the given graph , there is just one directed cycle : 2-->3-->4-->2. Hence, for all nodes on this cycle, the answer is yes and for others the answer is no.

Editor Image

?