Blockade

Time limit1sMemory limit128 MB

Summary

For each town, count planned visits ruined if it alone is removed, i.e. those crossing it plus visits to and from it.

Level: Medium7 of 10
Topics: Graph, DFS, Divide and conquer, Implementation
Solved: No attempts yet

Problem

There are exactly $n$ towns in Byteotia, and some pairs of towns are joined by bidirectional roads. Roads meet only inside towns (elsewhere they may cross by bridges, tunnels or flyovers), every pair of towns is joined by at most one direct road, and from any town you can reach every other town, directly or indirectly.

Each town is home to exactly one citizen, and every citizen wants to visit every other citizen once, in that citizen's home town. So $n \cdot (n - 1)$ visits are planned in total.

A group of protesters plans to blockade a single town so that it can no longer be entered, left, or even passed through. Some of the planned visits then become impossible: any visit that starts or ends in the blockaded town, and any visit between two other towns whose only route used to pass through it.

For every town, determine how many of the planned visits would become impossible if that town alone were blockaded.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 100000$ , $1 \le m \le 500000$ ): the number of towns and the number of roads. Towns are numbered from $1$ to $n$ .

Each of the next $m$ lines contains two integers $a$ and $b$ ( $1 \le a < b \le n$ ), describing a direct road between towns $a$ and $b$ .

Output

Output $n$ lines. Line $i$ must contain a single integer: the number of planned visits that could not take place if town $i$ were blockaded.

Hint

Examples1

Example 1
Input
```
5 5
1 2
2 3
1 3
3 4
4 5
```
Expected output
```
8
8
16
14
8
```