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 other vertices.

 

 

There 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.

 

 

For 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.

 

 

 

 

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <set>

 using namespace std;

 #define N 200010

 #define INF 0x3f3f3f3f

 struct node

 {

     int v, nxt;

 }edge[N];

 int head[N];

 int d[N], tot;

 void add(int u, int v)

 {

     edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++;

     edge[tot].v = u; edge[tot].nxt = head[v]; head[v] = tot++;

 }

 void bfs(int st, int n)

 {

     queue<int> que;

     d[st] = ;

     que.push(st);

     set<int> s1, s2;

     for(int i = ; i <= n; i++) {

         if(i != st) s1.insert(i);

     }

     while(!que.empty()) {

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

         for(int k = head[u]; ~k; k = edge[k].nxt) {

             int v = edge[k].v;

             if(!s1.count(v)) continue;

             s1.erase(v); //补图中当前能走到的并且还未更新过的

             s2.insert(v); //补图中走不到的还要扩展的

         }

         for(set<int>:: iterator it = s1.begin(); it != s1.end(); it++) {

             d[*it] = d[u] + ;

             que.push(*it);

         }

         s1.swap(s2); //还没更新过的

         s2.clear();

     }

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     while(t--) {

         memset(head, -, sizeof(head));

         memset(d, INF, sizeof(INF));

         int n, m;

         scanf("%d%d", &n, &m);

         for(int i = ; i < m; i++) {

             int u, v;

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

             add(u, v);

         }

         int st;

         scanf("%d", &st);

         bfs(st, n);

         bool f = ;

         for(int i = ; i <= n; i++) {

             if(i != st) {

                 if(f) printf(" ");

                 f = ;

                 if(d[i] == INF) printf("-1");

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

             }

         }

         puts("");

     }

     return ;

 }