「trips」E. Trips - seo实验室

trips

There are n

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 m

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 k

of his friends also go on the trip.

Note that the friendship is not transitive. That is, if a

and b are friends and b and c are friends, it does not necessarily imply that a and c

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 n

, m, and k (2≤n≤2⋅105,1≤m≤2⋅105, 1≤k<n

) — the number of people, the number of days and the number of friends each person on the trip should have in the group.

The i

-th (1≤i≤m) of the next m lines contains two integers x and y (1≤x,y≤n, x≠y), meaning that persons x and y become friends on the morning of day i. It is guaranteed that x and y

were not friends before.

Output

print exactly m

lines, where the i-th of them (1≤i≤m) contains the maximum number of people that can go on the trip on the evening of the day i

examples

Input

Copy

Output

Copy

Input

Copy

Output

Copy

Input

Copy

Output

Copy

Note

In the first example,

1,2,3

can go on day 3 and 4

In the second example,

2,4,5

can go on day 4 and 5

.
1,2,4,5
can go on day 6 and 7
.
1,2,3,4,5
can go on day 8
- .
In the third example,
- 1,2,5
can go on day 5
.
1,2,3,5

can go on day 6 and 7

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=b-1;i>=a;--i)
#define PB push_back
#define IS insert

const int N=2e5+10;
int ind[N],ans[N];

set<int> vec[N];
int U[N],V[N];

bool vis[N];

int n,m,K;

int sum=0;
queue<int> q;
/*
难点:
1.思维.    自己想的是怎样来融合，两个团，然后找到最大；实际上反着想更简单，我们进行拆边
2.无向图的一种连环反应，不知道怎样去边。   这时候就是STL的神奇时刻，直接找到。
但是有个地方： 迭代的时候删除，迭代器是对的，但是不能只依靠++，我们还得再erase的时候，
返回下一个位置
*/
void Top(){
	while(!q.empty()){
		++sum;
		int u=q.front();
		q.pop();

		set<int>::iterator it;
		for(it=vec[u].begin();it!=vec[u].end();){
			int v=*it;
			if(vis[v]){it++;continue;}

			vec[u].erase(it++);
			vec[v].erase(u);

			ind[v]--;
			if(!vis[v]&&ind[v]<K){
				vis[v]=1;
				q.push(v);
			}
		}
	}
}

int main(){
	scanf("%d %d %d",&n,&m,&K);
	rep(i,0,m){
		scanf("%d %d",&U[i],&V[i]);
		int u=U[i],v=V[i];
		vec[u].IS(v);
		vec[v].IS(u);
		ind[u]++;
		ind[v]++;
	}

	rep(i,1,n+1){
		if(ind[i]<K){
			vis[i]=1;
			q.push(i);
		}
	}

	Top();

	per(i,0,m){
	   ans[i]=n-sum;

	   int u=U[i],v=V[i];
	   if(vec[u].count(v))  ind[v]--,vec[u].erase(v);
	   if(vec[v].count(u))  ind[u]--,vec[v].erase(u);

	   if(!vis[v]&&ind[v]<K)vis[v]=1,q.push(v);
	   if(!vis[u]&&ind[u]<K)vis[u]=1,q.push(u);

	   Top();
	}
	rep(i,0,m)printf("%d\n",ans[i]);
	return 0;
}

E. Trips

trips

相关阅读

栏目导航

推荐阅读

热门阅读