题目描述

X 国是一个繁荣而强大的国家，由 $n$ 座城市（首都是城市 $1$）和 $\binom{n}{2}$ 条连接它们的单向道路组成。
这些道路恰好是所有不同的从编号小的城市通向编号大的城市的道路，即：

国王大 X 觉得现在的道路太单调了，所以他进行了 $m$ 次翻修。
每次翻修形如：给出两个不同的城市编号 $u,v$，并把 $u,v$ 之间的单向道路反向。

而在每次翻修之后，大 X 都会重新定一个首都。这个首都需要满足两个条件：

1. 它能通过单向道路到达所有点。
2. 它到所有点的距离之和最短。

其中 $i$ 到 $j$ 的距离是从 $i$ 到 $j$ 最少经过的道路数；如果 $i$ 无法到达 $j$，则距离为 $+\infty$。

请输出（每次翻修后）满足条件的首都到所有点的距离之和；如果不存在合法的首都，请输出 $-1$。

输入格式

第一行输入两个正整数 $n,m$。
接下来 $m$ 行，每行输入两个不同的正整数 $u,v$，表示一次翻修（将 $u,v$ 之间的单向道路反向）。

输出格式

对于每次翻修，输出一行：翻修后首都到所有点的距离之和；若不存在合法首都，输出 $-1$。

5 5
1 2
3 2
1 4
2 5
3 5

4
5
5
5
6

样例解释

样例 1 中，5 次修改后的首都分别可以为 $2,2,2,3,2$。

数据范围与提示