1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #include<vector> 6 #include<set> 7 using namespace std; 8  9 const int N = 200001;10 const int M = 50001;11 const int inf = 0x3f3f3f3f;12 int n, m;13 int d[N];14 int head[N];15 int cnt;16 struct edge{17     int nex;18     int v, w;19 }g[M];20 void add_edge(int u,int v,int w){21     g[cnt].v = v;22     g[cnt].w = w;23     g[cnt].nex = head[u];24     head[u] = cnt++;25 }26 27 void bfs(int s){28     int u, v, i;29     queue<int>q;30     set<int>a; //不邻接的点31     set<int>b; //未扩展的点32     set<int>::iterator it;33     for(i = 1; i <= n; ++i)34         a.insert(i);35     a.erase(s);36     q.push(s);37     while(!q.empty()){38         u = q.front();39         q.pop();40         for(i = head[u]; ~i; i = g[i].nex){41             v = g[i].v;42             if(!a.count(v))43                 continue;44             b.insert(v);45             a.erase(v);46         }47         for(it = a.begin(); it != a.end(); it++){48             d[*it] = d[u] + 1;49             q.push(*it);50         }51         a.swap(b);52         b.clear();53     }54 }55 int main(){56     int t, i, j, x, y, s, f;57     scanf("%d", &t);58     while(t--){59         scanf("%d %d", &n, &m);60         memset(d, inf, sizeof(d));61         memset(head, -1, sizeof(head));62         cnt = 0;63         for(i = 0; i < m; ++i){64             scanf("%d %d", &x, &y);65             add_edge(x, y, 1);66             add_edge(y, x, 1);67         }68         scanf("%d", &s);69         d[s] = 0;70         bfs(s);71         f = 0;72         for(i = 1; i <= n; ++i){73             if(i == s)continue;74             if(d[i] == inf)75                 printf("-1\n");76             else if(!f){77                 printf("%d", d[i]);78                 f = 1;79             }80             else81                 printf(" %d",d[i]);82         }83         printf("\n");84     }85     return 0;86 }