Codefroce 653E Bear and Forgotten Tree 2 (补图的联通块)

判断补图的联通块及连通性模板:第10个补图联通块

A tree is a connected undirected graph consisting of n vertices and n - 1 edges. Vertices are numbered 1through n.

Limak is a little polar bear. He once had a tree with n vertices but he lost it. He still remembers something about the lost tree though.

You are given m pairs of vertices (a1, b1), (a2, b2), ..., (am, bm). Limak remembers that for each i there was no edge between ai and bi. He also remembers that vertex 1 was incident to exactly k edges (its degree was equal to k).

Is it possible that Limak remembers everything correctly? Check whether there exists a tree satisfying the given conditions.

Input

The first line of the input contains three integers n, m and k () — the number of vertices in Limak's tree, the number of forbidden pairs of vertices, and the degree of vertex 1, respectively.

The i-th of next m lines contains two distinct integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the i-th pair that is forbidden. It's guaranteed that each pair of vertices will appear at most once in the input.

Output

Print "possible" (without quotes) if there exists at least one tree satisfying the given conditions. Otherwise, print "impossible" (without quotes).

Examples

Input

Output

possible

Input

Output

impossible

Note

In the first sample, there are n = 5 vertices. The degree of vertex 1 should be k = 2. All conditions are satisfied for a tree with edges 1 - 5, 5 - 2, 1 - 3 and 3 - 4.

In the second sample, Limak remembers that none of the following edges existed: 1 - 2, 1 - 3, 1 - 4, 1 - 5and 1 - 6. Hence, vertex 1 couldn't be connected to any other vertex and it implies that there is no suitable tree.

题目大意:题意很简单,有一颗n个节点的树,现在他忘了这个树的结构,只知道有m条边不可能存在,还记得1号点的出度为k,问是否可能存在一颗满足条件的树.

首先感谢龙队@winter2121.(太强了)

题目思路:

我们首先肯定想到与反图相关.所以首先构建反图,我们忽略1号点度数为k这个条件的话,这个题就是一个判断图的连通性的裸题了.我们加上这个条件,我们只需要把第一个点去掉.把剩下的图求联通块.这样很ok就求出来来图的联通块的个数.接下来我们需要判断几个点:

第一:首先 1号节点反图的出度要大于k 否则不存在树

第二:不能存在1号点链接不到的联通块,如果链接不到说明 1链接不到某些点,则说明无法够成树

第三:如果都能连接到需要看一下联通块的个数,如果联通块的个数大于k 还是不行小于等于k才可以,因为出度大于k了,所有联通块又包含所有点,小于k的联通块,从1出去瞎连k条即可.

经过判断所以,可以组成一个 1的度数为k 的连通图,连通图必有树,所以possible

求反图的联通块 :因为n太大 ,所以我们不好操作,我们用一个静态链表,将2-n各点存起来,毎标记过一个点,就删除一个点,复杂度 O(N+M) 龙队提供思路 .有点强

具体细节看代码叭:

#include <bits/stdc++.h>
#include<stdio.h>
#include<vector>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1000;
const int maxn=3e6+5;
const ll INF=100000000000005;
using namespace std;
ll n,m,p;
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;b/=2;a=(a*a)%mod;}return ans;}
int head[maxn];
struct node{
    int e,next;
}edge[maxn];
int pre[maxn],cur[maxn];
int vis[maxn];//标记每个点是否被访问
int d[maxn];//标记BFS中每个点是否被访问
int res[maxn];
ll cnt=0;
void addedge(int u,int v)
{
    edge[cnt]=node{v,head[u]};
    head[u]=cnt++;
    edge[cnt]=node{u,head[v]};
    head[v]=cnt++;
}
int main()
{
    int cot=0,judge=0;
    memset(head,-1,sizeof(head));
    scanf("%lld%lld%lld",&n,&m,&p);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        addedge(x,y);
        if(x==1||y==1) judge++;
    }
    judge=n-1-judge;//可行边
    if(judge<p) printf("impossible\n");//不可行
    else//可行之后需要判断图的连通性
    {
        int s=2;
        for(int i=2;i<=n;i++){
            pre[i]=i-1;
            cur[i]=i+1;
        }
        cur[n]=-1;pre[2]=-1;//首先去除1点建立一个静态链表
        for(int i=2;i<=n;i++)if(!vis[i]){//求出所有联通块
            queue<int>q;q.push(i);
            vis[i]=++cot;
            while(!q.empty())
            {
                int u=q.front();q.pop();
                for(int k=head[u];~k;k=edge[k].next)
                {
                    int e=edge[k].e;
                    if(!d[e]) d[e]=1;
                }
                for(int k=s;~k;k=cur[k])
                {
                    if(!d[k])
                    {
                        if(!vis[k])
                        {
                            cur[pre[k]]=cur[k];
                            pre[cur[k]]=pre[k];
                            if(k==s) s++;
                            vis[k]=cot;
                            q.push(k);
                        }
                    }
                    else
                        d[k]=0;
                }
            }
        }
        memset(d,0,sizeof(d));
        int f=0;
        for(int i=head[1];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            d[e]=1;
        }
        for(int i=2;i<=n;i++)
            if(!d[i])
                res[vis[i]]=1;
        for(int i=1;i<=cot;i++)
            if(!res[i]) {
                f=1;
                break;
            }
        if(f) puts("impossible");
        else
        {
            if(cot>p) printf("impossible\n");
            else printf("possible\n");
        }
    }
    return 0;
}
/***
5 4 1
1 2
2 3
4 2
4 1
***/

总结:去除标记点的时候使用静态链表太强了!减少了太多重复的判断!所以

纸上得来终觉浅，绝知此事要躬行。