시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB35231062.500%

문제

The City of ICPC is preparing for a party for its anniversary. As the mayor of the city, you would like to hold a parade in each of the districts in the city.

The parade route can be represented as a Directed Acyclic Graph. There are $N$ nodes (numbered from $1$ to $N$) that represent the districts in the city. There are $M$ directed edges (numbered from $1$ to $M$) that represent the one directional roads. By using road $j$, the parade can move from district $U_j$ to $V_j$, but not the other way around. It is known that all districts can be visited by the parade from the City Center, which resides in district $1$.

A road is $i$-critical if the road is used in all paths from district $1$ to district $i$. It is possible for a road to be $i$-critical for several values of $i$. You want to assess the number of $i$-critical roads for each $i$, as they are pivotal for the parade.

For each $i$ that satisfies $1 ≤ i ≤ N$, determine the number of $i$-critical roads.

입력

The first line consists of two integers $N$ $M$ ($2 ≤ N ≤ 100\, 000$; $N - 1 ≤ M ≤ 200\, 000$).

Each of the next $M$ lines consists of two integers $U_j$ $V_j$ ($1 ≤ U_j , V_j ≤ N$). The edges form a directed acyclic graph, and every node can be visited from node $1$. Furthermore, there will be no multi-edges, i.e., there will be at most one edge that directs two nodes.

출력

Output $N$ integers in a single line. Each of the integers represents the number of $i$-critical roads.

예제 입력 1

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

예제 출력 1

0 1 0 2 1 0

The following illustration depicts this sample. The numbers on the edges are the edge numbers.

It can be seen that edge $1$ is $2$-critical; edges $1$ and $3$ are $4$-critical; and edge $5$ is $5$-critical.

예제 입력 2

5 4
1 2
2 3
3 4
4 5

예제 출력 2

0 1 2 3 4