Problem G
Game of Two Choices

You are playing a game against SoCCat!

The game is played on a directed graph $G = (V, E)$ with $N$ vertices, numbered from $1$ to $N$. We denote $(u \to v)$ as a directed edge from vertex $u$ to vertex $v$. We denote $N(u)$ as the set of vertices such that there is an edge from $u$ to the vertices in $N(u)$. In other words, $N(u) = \{ v \mid (u \to v) \in E\} $.

Initially, a token is placed on some vertex $S$, and the game score is $0$. Each turn,

• Suppose the token is on vertex $u$.

• If $|N(u)| = 0$, the game ends.

• If $|N(u)| = 1$, the token moves to the only vertex in $N(u)$. The game score increases by $1$.

• If $|N(u)| \geq 2$, you must choose two different vertices $v_1, v_2 \in N(u)$ such that $v_1 \neq v_2$. Then, SoCCat can choose to either move the token to $v_1$ or $v_2$. The game score increases by $1$.

You would like to play the game as long as possible, so you want to maximize the game score. SoCCat would like to end the game as soon as possible, so they want to minimize the game score. Assuming both you and SoCCat play optimally, what is the maximum game score you can achieve? If the game can be played indefinitely, output -1. Otherwise, output the maximum game score.

Compute the above for all $S$ from $1$ to $N$!

Input

The first line of the input contains two integers $N$ and $M$ ($1 \leq N \leq 200\, 000$, $1 \leq M \leq 400\, 000$), the number of vertices and the number of edges in the graph.

The next $M$ lines each contain two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$, $u_i \neq v_i$), denoting a directed edge $(u_i \to v_i)$ from vertex $u_i$ to vertex $v_i$.

It is guaranteed that $(u_i \to v_i) \neq (u_j \to v_j)$ for all $i \neq j$. It is possible for the graph to be disconnected or contain cycles.

Output

Output $N$ integers. The $S$-th integer ($1 \leq S \leq N$) should be the maximum game score you can achieve when the token is initially placed on vertex $S$, assuming both you and SoCCat play optimally. If the game can be played indefinitely when the token is initially placed on vertex $S$, output -1 instead.

3 3
1 2
2 3
1 3

1 1 0

3 3
1 2
2 3
3 1

-1 -1 -1

6 6
2 1
3 2
4 5
5 6
6 4
4 2

0 1 2 2 4 3