In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N−1

InputThere are multiple test cases. The first line of input is an integer T(1≤T<35) denoting the number of test cases. For each test case, the first line contains two integers N(2≤N≤200000) and M(0≤M≤20000). The following M lines each contains two distinct integers u,v(1≤u,v≤N) denoting an edge. And S (1≤S≤N) is given on the last line.OutputFor each of T test cases, print a single line consisting of N−1 space separated integers, denoting shortest distances of the remaining N−1 vertices from S (if a vertex cannot be reached from S, output ``-1" (without quotes) instead) in ascending order of vertex number.Sample Input

1

2 0

1

Sample Output

1

题意：给定一个无向图，求它的补图中S到每一点的最短路。

思路：我们BFS，长度从0，1，2...慢慢试探，由于是补图，显然试探的次数不会太多就可以弄完，所以我们可以暴力一点，一次BFS，我们取出队首u，其最短距离是dis[u]，那么它没有被访问的点中（满足dis==-1），不与u相邻的点的最短距离是dis[u]+1，将其加入队首;  我们可以用set来表示未被访问的点。

由于S1.swap(S2)是两个set的指针交换，所以复杂度是O(1)，比较快的。主要复杂度再S.clear那里，clear的复杂度是元素个数，由于是补图，所以可以假设放进去之后几个回合内就删完了，复杂度不会太高。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn],dis[maxn],num[maxn];

int q[maxn],tot,cnt,S,N;

void add(int u,int v){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;

}

void BFS()

{

    dis[S]=;

    set<int>S1,S2;

    set<int>::iterator it;

    queue<int>q;

    q.push(S);

    rep(i,,N) if(i!=S) S1.insert(i);

    while(!q.empty()){

        int u=q.front(); q.pop();

        for(int i=Laxt[u];i;i=Next[i]){

            int v=To[i]; if(S1.find(v)==S1.end()) continue;

            S1.erase(v); S2.insert(v);

        }

        for(it=S1.begin();it!=S1.end();it++) dis[*it]=dis[u]+,q.push(*it);

        S1.swap(S2); S2.clear();

    }

}

int main()

{

    int T,M,u,v;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&M);

        cnt=; rep(i,,N) Laxt[i]=,dis[i]=-;

        rep(i,,M){

            scanf("%d%d",&u,&v);

            add(u,v); add(v,u);

        }

        scanf("%d",&S);

        BFS();

        rep(i,,N){

             if(i!=S){

                if(i!=N) printf("%d ",dis[i]);

                else printf("%d\n",dis[i]);

             }

        }

    }

    return ;

}