Given a directed graph $G=(V,E)$ with $n$ vertices, it is guaranteed that vertex $1$ can reach all other vertices.

We say that vertex $u$ dominates vertex $v$ if, after removing vertex $u$, there is no path from $1$ to $v$. Specifically, every vertex dominates itself.

You need to calculate, for each vertex, how many vertices it dominates.

Input

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $u$ and $v$, describing a directed edge from $u$ to $v$.

Output

Output a single line containing $n$ integers, where the $i$-th integer describes the number of vertices dominated by vertex $i$.

Constraints

For all test cases, $1 \leq n \leq 5 \times 10^5, 1 \leq m \leq 10^6$.

Examples

Input 1

3 3
1 2
1 3
2 3

Output 1

3 1 1

Input 2

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

Output 2

5 2 1 1 1