008 - 高速道路網

問題文

ヅイア国の高速道路網は、都市(地点)とそれらを結ぶ道路から構成されています。イワシロ地域を縦断するイワシロ自動車道は国の重要な幹線です。 イワシロ自動車道の上り線は以下のように建設されています。

• $1$ から $N$ の番号が割り当てられた $N$ 個の都市（地点）がある。
• 地点$1$が起点、地点$N$が終点である。
• 道路は一方通行で、ある地点とある地点を直接結ぶ道路は多くても$１$つしかない。
• どの地点にも必ず起点からたどり着くことができ、どの地点からも終点にたどり着ける。
• どのように道路をたどっていっても、同じ地点に戻ることはない。

ヅイア国はイワシロ自動車道の上り線の調査を行うことにしました。この調査では、上り線の各地点について、その地点を通って起点から終点へ向かうすべての経路の長さの和を求める必要があります。

課題

地点の数と道路の情報が与えられる。各地点$i$について、起点から地点$i$を通って終点へたどり着くすべての経路の長さの総和を出力するプログラムを作成せよ。ただし、経路の長さは経由した道の数とする。

入力

入力は以下の形式で与えられる。

$N \  M$
$u_{1} \  v_{1}$
$u_{1} \  v_{1}$
$\vdots$
$u_{M} \  v_{M}$

１行目に地点の数$N\ (2 \leq N \leq 50)$と道路の数$M\ (N - 1 \leq M \leq N \times (N - 1) / 2)$が与えられる。
続く$M$行に$i$番目の道路の出発地点$u_{i}$と到着地点$v_{i}\ (1 \leq u_{i} \lt v_{i} \leq N)$が与えられる。

出力

出力は $N$ 行である。$i$行目に、地点$i$を通る経路の長さの総和を出力する。

入出力例

入力例1

3 3
1 2
2 3
1 3

出力例1

3
2
3

---

起点から地点1を通って終点へと向かう経路は $1 \rightarrow 2 \rightarrow 3, 1 \rightarrow 3$ の二つであり、その長さの総和は $3$ となる。
起点から地点2を通って終点へと向かう経路は $1 \rightarrow 2 \rightarrow 3$ の一つであり、その長さの総和は $2$ となる。
起点から地点3を通って終点へと向かう経路は $1 \rightarrow 2 \rightarrow 3, 1 \rightarrow 3$ の二つであり、その長さの総和は $3$ となる。

入力例2

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

出力例2

14
11
7
7
11
14

---