A communication network consists of $N$ computers and $M$ lines. The computers are numbered from $1$ to $N$. A single line allows two distinct computers to communicate bidirectionally. A communication network is said to be connected if any two computers in the network can communicate using one or more lines. If there exists a pair of computers that cannot communicate, the network is said to be disconnected.

The risk of a line $c$ in the communication network is defined as follows: For each computer $i$ in the network, if the remaining network is disconnected after removing computer $i$, then computer $i$ is called a critical computer. The risk of $c$ is defined as the number of critical computers when $c$ is removed from the initial communication network.

Write a program that takes the communication network as input and calculates the risk of each line.

Implementation Details

You must implement the following function:

vector<int> find_num_critical(int N, vector< pair<int, int> > E)

• This function is called exactly once.
• The integer $N$ given as an argument represents the number of computers $N$.
• The size of the array $E$ given as an argument is $M$. Each element of the array $E$ represents a single line and is given as a pair of distinct computer numbers.
• This function must calculate the risk of each line and return it in an integer array of length $M$. The order of the risks in the array must correspond to the order of the lines given in $E$.

You must not execute any input/output functions in any part of the source code you submit.

Constraints

• $2 \le N \le 250\,000$
• $1 \le M \le 1\,000\,000$
• Each line connects two distinct computers.
• There may be multiple lines connecting the same pair of computers.
• The initial communication network is connected.

Subtasks

1. (5 points) $N \le 200$, $M \le 500$
2. (11 points) $N \le 1\,000$, $M \le 2\,500$
3. (7 points) $N = M$
4. (13 points) For $k \ge 2$ distinct computers $v_1, v_2, \dots, v_k$ and $k$ distinct lines $c_1, c_2, \dots, c_k$, if line $c_i$ connects two computers $v_i, v_{i+1}$ ($1 \le i \le k-1$) and line $c_k$ connects two computers $v_k, v_1$, then the $k$ lines $c_1, c_2, \dots, c_k$ form a cycle. Two cycles are the same if the sets of lines forming each cycle are identical. For each line $c$ in the communication network, there exists at most one cycle containing $c$.
5. (25 points) $N \le 8\,000$, $M \le 250\,000$
6. (29 points) $N \le 100\,000$, $M \le 250\,000$
7. (10 points) No additional constraints.

Scoring

The solution is considered correct if the length of the array returned by find_num_critical is $M$ and all elements in the returned array match the corresponding elements in the correct answer array.

Examples

Input 1

5 5
1 5
5 2
2 3
2 4
2 5

Output 1

4 2 4 4 2

Note

The initial communication network is given as follows:

For example, if the line connecting computer 1 and computer 5 is removed, the network becomes as follows:

In this network, the critical computers are 2, 3, 4, and 5. Note that computer 1 is not a critical computer because the remaining network is connected when it is removed.

If one of the lines connecting computer 2 and computer 5 is removed, the network becomes as follows:

In this network, the critical computers are 2 and 5.

Sample grader

The sample grader reads input in the following format:

• Line 1: $N, M$
• Line $1 + i$ ($1 \le i \le M$): $a_i, b_i$

The pair $a_i, b_i$ means that computer $a_i$ and computer $b_i$ are connected by a line.

The sample grader outputs the following:

• Line 1: The array returned by the function find_num_critical

Note that the sample grader may differ from the actual grader used for evaluation.