For a directed graph $G$ with $n$ vertices and $m$ edges (vertices are numbered $1 \sim n$), we define the function $f(u, G)$ as follows:

1. Initialize the return value $cnt = 0$, and let $G' = G$.
2. Enumerate vertices $v$ from $1$ to $n$ in order. If in the current graph $G'$, there exists a path from $u$ to $v$ and a path from $v$ to $u$, increment $cnt$ by $1$, and remove vertex $v$ and all edges connected to it from $G'$.
3. After step 2, the return value $cnt$ is the function value.

Given a directed graph $G$, calculate the value of $h(G) = f(1, G) + f(2, G) + \dots + f(n, G)$.

Furthermore, let $G_i$ be the graph after removing the first $i$ edges (in the order they appear in the input) ($1 \le i \le m$). Calculate the values of $h(G_i)$ for all $i$.

Input

The input is read from standard input.

The first line contains two integers $n$ and $m$, representing the number of vertices and edges in the graph.

The next $m$ lines each contain two integers. The $i$-th line contains two integers $x_i, y_i$, representing a directed edge $x_i \to y_i$.

It is guaranteed that $x_i \neq y_i$ and no edge is given more than once.

Output

Output to standard output.

Output a single line containing $m + 1$ integers. The first integer represents the value $h(G)$ for the complete graph $G$ provided. The $i$-th integer ($2 \le i \le m + 1$) represents $h(G_{i-1})$.

Examples

Input 1

4 6
2 3
3 2
4 1
1 4
2 1
3 1

Output 1

6 5 5 4 4 4 4

Note

For the given complete graph $G$: 1. $f(1, G) = 1$, vertex $1$ is removed during the process. 2. $f(2, G) = 1$, vertex $2$ is removed during the process. 3. $f(3, G) = 2$, vertices $2, 3$ are removed during the process. 4. $f(4, G) = 2$, vertices $1, 4$ are removed during the process.

Examples

Input 2

See graph/graph2.in in the contestant directory.

Output 2

See graph/graph2.ans in the contestant directory.

Constraints

For all test data: $2 \le n \le 1000$, $1 \le m \le 2 \times 10^5$, $1 \le x_i, y_i \le n$.

The specific limits for each test case are shown in the table below: