里海城际快递公司（ICPC）正在启动一项快递服务，在里海附近的各个城市之间运送包裹。该公司计划雇佣快递员在这些城市之间运送包裹。

每个快递员都有一个常驻城市和一个目的地城市，并且所有快递员的出行时间表完全相同：他们在 9:00 离开常驻城市，在 12:00 到达目的地城市，在 14:00 离开目的地城市，并在 17:00 返回常驻城市。当快递员在他们的常驻城市或目的地城市时，他们可以从客户那里接收包裹和/或将包裹投递给客户。他们也可以与同时在该城市的其他快递员交接包裹。由于 ICPC 提供的是个性化服务，包裹绝不会被留在仓库或其他设施中以便日后取走——除非包裹已经到达目的地，否则快递员必须将包裹随身携带（在白天或夜间），或者将其移交给另一位快递员。

公司将指导快递员进行包裹交接，以确保任何包裹总能被送达目的地。至少希望如此！如果既可以将包裹从城市 $u$ 送达城市 $v$，也可以将包裹从城市 $v$ 送达城市 $u$，我们就称城市 $u$ 和 $v$ 是连通的。为了评估招聘过程的效率，公司希望在每雇佣一名快递员后，求出连通的城市对 $(u, v)$ 的数量（$1 \le u < v \le n$）。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，其中 $n$（$2 \le n \le 2 \cdot 10^5$）是城市的数量，$m$（$1 \le m \le 4 \cdot 10^5$）是将要雇佣的快递员数量。快递员按雇佣顺序从 $1$ 到 $m$ 编号。

接下来的 $m$ 行中，第 $i$ 行包含两个不同的整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），分别表示快递员 $i$ 的常驻城市和目的地城市。

输出格式

输出 $m$ 个整数，表示在雇佣前 $1, 2, \dots, m$ 名快递员后，连通的城市对数量。

样例

输入样例 1

4 4
1 2
2 3
4 3
4 2

输出样例 1

1
2
4
6

说明

样例 1 说明

1. 雇佣第一名快递员后，城市 1 和 2 连通。
2. 雇佣第二名快递员后，城市 2 和 3 连通。然而请注意，城市 1 和 3 仍然不连通。尽管有一名快递员在城市 1 和 2 之间往返，另一名快递员在城市 2 和 3 之间往返，但他们永远不会相遇。

3. 雇佣第三名快递员后，城市 3 和 4 连通，且城市 2 和 4 连通。例如，将包裹从城市 2 送达城市 4 的一种方法是：

   • 在 19:00 于城市 2 将包裹交给快递员 2；
   • 第二天，快递员 2 于 12:00 到达城市 3，并将包裹交给同样在城市 3 的快递员 3；
   • 在 18:00，快递员 3 将包裹送达城市 4。

4. 雇佣第四名快递员后，所有六对城市都已连通。