题目描述

国家 N 由 $n$ 座城市组成，城市编号为 $1$ 到 $n$，但这个国家现在完全没有道路！

总统决定在接下来的 $m$ 天里修建 $m$ 条道路，每天恰好修建一条新道路。为了支持人口迁移，还决定把所有道路都修成单向道路，并且规划路网时要满足：如果存在从城市 $i$ 到城市 $j$ 的路径，那么就不存在从城市 $j$ 到城市 $i$ 的路径。

为了让人民更喜欢这些新道路，国家 N 决定每天举行一系列城市汽车巡游。每辆巡游车从某座城市出发，沿着截至当天已经建好的道路行驶，最后在某座城市结束路线。允许起点和终点是同一座城市，也就是说车辆可以不沿任何道路移动。

组织者既希望取悦居民，又希望节省司机燃料，因此每天会按照如下规则选择一组路线：

1. 每座城市都必须被某辆巡游车访问。访问包括一条路线的起点、终点以及所有中间城市。
2. 任何城市都不能被巡游车访问超过一次。
3. 使用的车辆总数必须最少。

国家 N 的交通部已经规划好了未来 $m$ 天每天修建的道路。现在交通部代表请你对每一天求出：在建好前 $i$ 天的道路后，举行巡游最少需要多少辆车。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示国家 N 的城市数量以及修路天数。

接下来 $m$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 天会修建一条从城市 $u_i$ 到城市 $v_i$ 的单向道路。

允许修建一条此前已经在两座城市之间修建过的道路。

保证在修建任意道路之后，如果存在从城市 $a$ 到城市 $b$ 的路径，就不存在从城市 $b$ 到城市 $a$ 的路径。

输出格式

输出 $m$ 个整数，第 $i$ 个整数表示修建前 $i$ 条道路之后，巡游所需的最少车辆数。

样例 1

输入

3 3
1 2
1 3
2 3

输出

2 2 1

样例 2

输入

5 4
1 2
2 3
4 2
2 5

输出

4 3 3 3

样例 3

输入

4 4
1 2
1 2
3 4
3 4

输出

3 3 2 2

样例解释

在第一个样例中，建好前两条道路后，仍然至少需要两辆车。例如，一辆车可以从城市 $1$ 开到城市 $2$，另一辆车从城市 $3$ 出发并在城市 $3$ 结束。建好全部道路后，一辆车即可沿路线 $1 \to 2 \to 3$ 完成巡游。

在第二个样例中，建好所有道路后，如果只考虑覆盖所有城市，似乎可以只用两辆车。但题目要求任何城市不能被超过一辆车访问，这一条件阻止了这种方案。

评分方式

本题共有若干组测试。每组分数只有在通过该组所有测试以及表中指定的部分前置测试组后才会获得。Offline 检查表示该组测试结果只会在比赛结束后公布。