对于一张 $n$ 个点 $m$ 条边的有向图 $G$ (顶点从 $1\sim n$ 编号)，定义函数 $f(u,G)$ :

1. 初始化返回值 $cnt=0$，图 $G\prime =G$。
2. 从 $1$ 至 $n$ 按顺序枚举顶点 $v$，如果当前的图 $G\prime$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在，则将 $cnt+1$，并在图 $G\prime$ 中删去顶点 $v$ 以及与它相关的边。
3. 第 $2$ 步结束后，返回值 $cnt$ 即为函数值。

现在给定一张有向图 G,请你求出 $h(G)=f(1,G)+f(2,G)+\cdots +f(n,G)$ 的值。

更进一步地，记删除（按输入顺序给出的）第 $1\sim i$ 条边后的图为 $G_i(1\le i\le m)$，请你求出所有 $h(G_i)$ 的值。

输入格式

第一行两个整数 $n,m$ 表示图的点数与边数。

接下来 $m$ 行每行两个整数，第 $i$ 行的两个整数 $x_i,y_i$ 表示一条有向边 $x_i\to y_i$。

数据保证 $x_i\ne y_i$ 且同一条边不会给出多次。

输出格式

输出一行 $m+1$ 个整数，其中第一个数表示给出的完整图 $G$ 的 $h(G)$ 值。第 $i(2\le i\le m+1)$ 个整数表示 $h(G_{i-1})$。

样例一

input

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

output

6 5 5 4 4 4 4

explanation

对于给出的完整图 $G$:

1. $f(1,G)=1$，过程中删除了顶点 $1$。
2. $f(2,G)=1$，过程中删除了顶点 $2$。
3. $f(3,G)=2$，过程中删除了顶点 $2,3$。
4. $f(4,G)=2$，过程中删除了顶点 $1,4$。

样例二

见附加文件中 ex_graph2.in 与 ex_graph2.ans。

限制与约定

对于所有测试数据：$2\le n\le 1000,1\le m\le 2\times {10}^5,1\le x_i,y_i\le n$。

每个测试点的具体限制见下表:

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载