Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito and his friends love Chess and they frequently play against each other. They numbered themselves from $1$ to $N$ (including Fito) in a convenient way. For some pairs of friends, $a_i$ and $b_i$ (with $a_i < b_i$), they already  know that $a_i$ always beats $b_i$. Also, if $a$ beats $b$ and $b$ beats $c$, it is implicitly known that $a$ beats $c$. This information is consistent, which means that player $a$ doesn´t beat him/herself (not even implicitly) and for every pair of players $a$ and $b$, either $a$ beats $b$, or $b$ beats $a$, or their expected match-result is not known.

All friends are now organizing a Chess tournament. Since there are too many participants, they want to split it into groups, in such a way that each group will play in a different room and all players in the same group will have to play against each other.

The tournament should be really exciting, therefore, no group can contain two players for which their expected match-result is known in advance (or implicitly), even if this means that there have to be some groups with a single player. To satisfy this condition, they computed the minimum number of rooms they would need, and it turns out that they are short by one. Therefore, they want to check if removing one player will solve the problem. More specifically, they want to know for each player if removing him or she will reduce the total number of rooms needed.

Input

The first line of input contains two integers $N$ ($2 \leq N \leq 10^5$) the number of Fito's friends (including Fito), and $M$ ($1\leq M\leq 2*10^5$) the number of pairs of friends whose match-result is known in advance. The following $M$ lines will contain two integers $a_i,\ b_i$ ($1 \leq a_i,\ b_i \leq N$, $a_i < b_i$), which means that $a_i$ beats $b_i$.

Output

Sample test(s)