必威体育Betway必威体育官网
当前位置:首页 > IT技术

E. Trips

时间:2019-10-01 14:14:29来源:IT技术作者:seo实验室小编阅读:78次「手机版」
 

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

4 4 2
2 3
1 2
1 3
1 4

Output

Copy

0
0
3
3

Input

Copy

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

Output

Copy

0
0
0
3
3
4
4
5

Input

Copy

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

Output

Copy

0
0
0
0
3
4
4

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;
    }
    

相关阅读

社交巨头三国杀:微信、WhatsApp、Line到底有啥区别?

美团创始人王兴在《九败一胜》里提出过一个“四纵三横”的理论:四纵即互联网的四大热门领域——资讯、交流(社交)、娱乐、商务。在这

Oracle创建新用户并授权

/*第1步:创建临时表空间 */create temporary tablespace root_temp tempfile 'D:\app\Administrator\product\11.2.0\dbhome

e.printStackTrace()

catch(Exception e){e.printStackTrace() ;}当try语句中出现异常是时,会执行catch中的语句,java运行时系统会自动将catch括号中的Ex

build-essential作用

编译工程时到最后的时候,系统报错。错误原因竟然是乱码,但是我的系统上解密已经登录。莫名其妙啊!sudo apt-get install build-essen

win7 64位安装packet.dll

装不上的,放弃吧 下载一个winpcap,装上就可以了 之后安装软件就不会报找不到packet.dll的错误了

分享到:

栏目导航

推荐阅读

热门阅读