Network

Time limit2.5sMemory limit1024 MB

Summary

For each link, count the computers whose removal disconnects the network after that link is deleted, and print one count per link.

Level: Medium7 of 10
Topics: Graph, DFS, Tree
Solved: No attempts yet

Problem

A network is made of $N$ computers and $M$ links. The computers are numbered from $1$ to $N$ . Each link lets two different computers communicate in both directions. A network is connected if any two of its computers can communicate using one or more links. If there is a pair of computers that cannot communicate, the network is disconnected.

The danger level of a link $c$ is defined as follows.

For each computer $i$ in the network, if the remaining network is disconnected after removing computer $i$ , computer $i$ is called a dangerous computer.
The danger level of $c$ is the number of dangerous computers in the initial network after removing $c$ .

Input

The first line contains two integers $N$ and $M$ . ( $2 \le N \le 250\,000$ , $1 \le M \le 1\,000\,000$ )

Each of the next $M$ lines contains $x_i$ and $y_i$ . Link $i$ connects computer $x_i$ and computer $y_i$ . ( $1 \le x_i, y_i \le N$ , $x_i \neq y_i$ )

Output

Print $M$ lines. The $i$ -th line is the danger level of link $i$ .

Constraints

$2 \le N \le 250\,000$
$1 \le M \le 1\,000\,000$
Each link connects two different computers.
Multiple links may connect the same pair of computers.
The initial network is connected.

Examples1

Example 1
Input
```
5 5
1 5
5 2
2 3
2 4
2 5
```
Expected output
```
4
2
4
4
2
```