#P18539. Slothful Secretary
Slothful Secretary
Slothful Secretary
一所学校有 n 间教室,编号为 1 到 n。任意两间教室之间恰有一条走廊;为方便学生通行,每条走廊只能沿一个方向通过。
学校的秘书要给每间教室的班长各送一份通知,每间教室恰有一位班长。为了减少自己的工作,他可以把多份通知交给某位班长,请这位班长代为分发。班长能够把通知送到另一间教室,当且仅当他可以沿走廊从自己的教室走到那间教室,并再沿走廊回到自己的教室。只要在全部分发完毕后能够回到自己的教室,班长愿意承担任意多次分发任务。
称一个班长集合为完整集合,当且仅当秘书能把所有通知分配给这个集合中的班长,并由他们代为分发,使每一间教室都收到通知。求完整集合的最小可能大小。
你需要处理 q 次修改。最初,对于每一对 1<=i<j<=n,连接 i、j 的走廊均从 i 指向 j。每次修改把指定的一条走廊反向。请在每次修改之后输出当前完整集合的最小可能大小。修改依次生效,同一条走廊可以反复反向。
输入格式
第一行包含两个整数 n 和 q。
接下来 q 行,第 k 行包含两个整数 u_k、v_k,表示第 k 次修改反向连接这两间教室的走廊。
- 。
- 。
输出格式
对每次修改输出一行,一个整数,表示该次修改之后的答案。
原样例
输入:
4 5
2 3
3 4
1 3
2 3
3 4
输出:
4
2
1
1
2
样例说明
下列两幅原图分别表示第二次修改后与第四次修改后的走廊方向。

第二次修改之后,秘书可以把 3 份通知交给教室 3 的班长,把 1 份交给教室 1 的班长。教室 3 的班长能把通知送到教室 2 和 4,然后返回教室 3。

第四次修改之后,秘书可以把全部 4 份通知交给教室 4 的班长。这位班长能送达其余所有教室并返回教室 4。