Sparse Graph

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N = 200010, M = 2 * 20010, mod = 1e9 + 7;
using namespace std;
int h[N], e[M], ne[M], dist[N], idx = 0;
int n, m, s;
bool st[N], direct[N];
void add(int x, int y){
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}
void bfs(){
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    st[s] = true;
    int cnt = 1;
    while(!q.empty() && cnt < n){
        memset(direct, 0, (n + 1) * sizeof(bool));
        int t = q.front();
        q.pop();
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            direct[j] = true;
        }
        for(int i = 1; i <= n; i ++){
            if(!st[i] && !direct[i]){
                q.push(i);
                cnt ++;
                dist[i] = dist[t] + 1;
                st[i] = true;
            }
        }
    }
}
int main()
{
    CLOSE;
    int T;
    cin >> T;
    while(T --){
        cin >> n >> m;
        idx = 0;
        //别sizeof多了，浪费时间
        memset(h, -1, (n + 1) * sizeof(int));
        memset(dist, 0x3f, (n + 1) * sizeof(int));
        memset(st, 0, (n + 1) * sizeof(bool));
        for(int i = 1; i <= m; i ++){
            int x, y;
            cin >> x >> y;
            add(x, y), add(y, x);
        }
        cin >> s;
        bfs();
        for(int i = 1; i <= n; i ++){
            if(i == s) continue;
            cout << (dist[i] == 0x3f3f3f3f ? -1 : dist[i])<< " ";
        }
        cout << endl;
        printf("\n");
    }
    return 0;
}