KOI City consists of $N$ buildings numbered from $1$ to $N$, and $M$ bidirectional roads numbered from $1$ to $M$ connecting the buildings. Each road connects two distinct buildings; specifically, the $i$-th road connects building $u_i$ and building $v_i$ bidirectionally. It is possible to travel between any pair of buildings using the roads.

Originally, all roads in KOI City were free to use, meaning the toll of every road was $0$. However, in order to overcome the city’s financial difficulties, the mayor Jeong-ol plans to impose tolls on the roads over the course of $M$ days.

Specifically, on the $i$-th day, the toll of the $i$-th road is changed to $1$. As a result, after all $M$ days have passed, every road will have a toll of $1$.

Define the minimum travel cost between building $a$ and building $b$ as the minimum total toll required to move from building $a$ to building $b$, and denote it by $f(a, b)$. If $a = b$, then $f(a, b) = 0$.

The total cost of the road network is defined as the sum of the minimum travel costs between all possible pairs of buildings. That is, after computing $f(a, b)$ for all natural numbers $a, b$ satisfying $1 \le a, b \le N$, their sum is the total cost of the road network. In mathematical notation, the total cost is

$$\sum_{a=1}^{N} \sum_{b=1}^{N} f(a, b)$$

Jeong-ol wants to analyze how the changes in tolls affect the citizens. Help Jeong-ol by computing the total cost of the road network after the end of the $i$-th day, for each $i$.

Constraints

All given values are integers.

• $2 \le N \le 500$
• $N - 1 \le M$
• For $1 \le i \le M$, $u_i \ne v_i$
• For $1 \le i \le M$, $1 \le u_i, v_i \le N$
• There is at most one road connecting any unordered pair of distinct buildings.
• It is possible to travel between any pair of buildings using the roads.

Scoring

1. (10 points) $N \le 5$
2. (15 points) $N \le 50$
3. (30 points) $M \le 500$
4. (45 points) No additional constraints

Input Format

The first line contains two integers $N$ and $M$ separated by a space.

The next $M$ lines describe the roads. The $i$-th of these lines ($1 \le i \le M$) contains two integers $u_i$ and $v_i$ separated by a space.

Output Format

Output a total of $M$ lines. The $i$-th line ($1 \le i \le M$) should contain the total cost of the road network after the end of the $i$-th day.

Example

Example 1

Input

4 4
1 2
2 3
3 1
3 4

Output

0
6
10
16

Explanation

After 4 days, the minimum travel costs between buildings can be represented by the following table:

Therefore, after the end of the 4th day, the total cost of the road network is [ 0 + 1 + 1 + 2 + 1 + 0 + 1 + 2 + 1 + 1 + 0 + 1 + 2 + 2 + 1 + 0 = 16. ]

Example 2

Input

4 4
2 3
3 1
3 4
1 2

Output

0
8
14
16