Highway Network

The highway network in Zuia consists of cities (points) and the roads that connect them. The Ivashilo Motorway, which runs through the Ivashilo region, is an important national artery. The upstream sections of the Ivashilo Motorway are constructed as follows.

• There are $N$ cities (points) assigned the numbers $1$ to $N$.
• Point $1$ is the starting point and point $N$ is the ending point.
• Roads are one-way, and there is only one road at most that directly connects one point to another.
• Any point can always be reached from any starting point, and any point can be reached from any ending point.
No matter how you follow the road, you will never return to the same point.

The Zuia nation decided to survey the upstream line of the Iwashiro Expressway. In this survey, for each point on the upstream line, we need to find the sum of the lengths of all the paths that go from the starting point to the end point through that point.

The number of points and the information about the road are given. Write a program that outputs the sum of the lengths of all routes from the starting point through point $i$ to the end point for each point $i$. Let the length of the path be the number of roads traversed.

Input

Input is given in the following form.

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
:
$u_M$ $v_M$

In the first line, the number of points $N$ ($2 \leq N \leq 50$) and the number of roads $M$ ($N-1 \leq M \leq N \times (N-1)/2$) are given. In the following $M$ lines, the starting point $u_i$ and the arrival point $v_i$ ($1 \leq u_i < v_i \leq N$) of the $i$-th road are given.

Output

The output consists of $N$ lines, where the $i$-th line is the total length of the path through point $i$.    

Sample Input and Output

Sample Input 1

3 3
1 2
2 3
1 3

Sample Output 1

3
2
3

There are 2 routes from the starting point to the ending point through 1: 1 $\rightarrow$ 2 $\rightarrow$ 3, 1 $\rightarrow$ 3, and the total length is 3.
There are 1 routes from the starting point to the ending point through 2: 1 $\rightarrow$ 2 $\rightarrow$ 3, and the total is 2.
There are 2 routes from the starting point to the ending point through 3: 1 $\rightarrow$ 2 $\rightarrow$ 3, 1 $\rightarrow$ 3, and the total is 3.

Sample Input 2

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

Sample Output 2

14
11
7
7
11
14

 

---