题目大意:
一共有nn个人,他们开始互不认识,而每天早上不认识的两个人会变成朋友。一共有mm天,每天晚上有的人要去旅行,去旅行的人必须满足ta有至少kk个朋友也去旅行
求每天去旅行的最大人数
相关题目:「Codeforces」1037E Trips

E. Trips

time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

There are nn persons who initially don't know each other. On each morning, two of them, who were not friends before, become friends.

We want to plan a trip for every evening of mm days. On each trip, you have to select a group of people that will go on the trip. For every person, one of the following should hold:

  • Either this person does not go on the trip,
  • Or at least kk of his friends also go on the trip.

Note that the friendship is not transitive. That is, if aa and bb are friends and bb and cc are friends, it does not necessarily imply that aa and cc are friends.

For each day, find the maximum number of people that can go on the trip on that day.

Input

The first line contains three integers nn, mm, and kk — the number of people, the number of days and the number of friends each person on the trip should have in the group.

The ii-th of the next mm lines contains two integers xx and yy , meaning that persons xx and yy become friends on the morning of day ii. It is guaranteed that xx and yy were not friends before.

Output

Print exactly mm lines, where the ii-th of them contains the maximum number of people that can go on the trip on the evening of the day ii.

Examples

input

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

output

0
0
3
3
0
0
0
3
3
4
4
5
0
0
0
0
3
4
4

Note

In the first example,

1,2,31,2,3 can go on day 33 and 44.

In the second example,

2,4,52,4,5 can go on day 44 and 55.
1,2,4,51,2,4,5 can go on day 66 and 77.
1,2,3,4,51,2,3,4,5 can go on day 88.

In the third example,

1,2,51,2,5 can go on day 55.
1,2,3,51,2,3,5 can go on day 66 and 77.

Solution

用到了一个常用技巧:倒着操作,因为动态加边完全图不好维护,所以可以倒着做看删掉边时那些点会被炸掉。

每次删掉一条边,如果两端的点的度数 k\leq k,那么这个点就不能被选,所以将这个点删掉,再看与其相连的点的度数是否 k\leq k,整个过程与拓扑排序过程相似。

时间复杂度 O(n)O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
#define N 200005

int n, m, k, u[N], v[N];
int du[N], r, ans[N];
queue<int> q; int vis[N];
vector<int> d[N];

void del() {
while(!q.empty()) {
int x=q.front(); q.pop();
for(int y:d[x])if(y&&!vis[y]) {
--du[y];
if(du[y]<k) q.push(y),vis[y]=1,--r;
}
}
}

int main() {
read(n),read(m),read(k); r=n;
int x, y;
rep(i,1,m) read(x),read(y),u[i]=x,v[i]=y,++du[x],++du[y],d[x].push_back(y),d[y].push_back(x);
rep(i,1,n)if(du[i]<k) q.push(i),vis[i]=1,--r;
del();
ans[m]=r;
for(int i=m;i;--i) {
x=u[i], y=v[i];
if(!vis[x]&&!vis[y]) {
du[x]--, du[y]--;
if(du[x]<k) q.push(x), vis[x]=1,--r;
if(du[y]<k) q.push(y), vis[y]=1,--r;
for(unsigned i=0;i<d[x].size();++i)if(d[x][i]==y) d[x][i]=0;
for(unsigned i=0;i<d[y].size();++i)if(d[y][i]==x) d[y][i]=0; //delete
del();
}
ans[i-1]=r;
}
rep(i,1,m) printf("%d\n", ans[i]);
return ~~(0^_^0);
}