UOJ Logo

NOI.AC

1S 512MB
统计

翘课

刚入学,班上一共有 n 名同学,互相都不认识。每天,班上会多出一对朋友$(x_i,y_i),x_i\not=y_i$,在这对新朋友确定后,大家会一起商量翘课的事情。一个人翘课,仅当他的至少 K 个朋友也翘课。问每天最多会有多少人翘课。

输入格式

第一行三个整数,分别是同学数量n,总天数 m,和至少 K 个朋友。

后面 m 行每行两个数$x_i,y_i$。这对$x_i,y_i$之前没有出现过。

输出格式

一共 m 行,每行一个数表示答案,即当天的新朋友关系确定后,最多会有多少人翘课。

样例1

输入

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

输出

0
0
0
3
4
4
5
5

样例2

点此下载

数据范围

10% $2\le n,m\le 500,k=1$

20% $2\le n,m\le 200000,k=1$

40% $2\le n,m\le 2000,k=2$

70% $2\le n,m\le 2000,k< n $

100% $2\le n,m\le 200000,1\le k < n $