翘课

刚入学，班上一共有 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$