#include <bits/stdc++.h>

using namespace std;

int T, n, m, k, u, v, f[100001];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i) f[i] = 1e9;
    f[k] = 0;
    while (m--) {
      scanf("%d%d", &u, &v);
      int tu = min(f[v], f[u] + 1), tv = min(f[u], f[v] + 1);
      f[u] = tu;
      f[v] = tv;
    }
    for (int i = 1; i < n; ++i) printf("%d ", f[i] == 1e9 ? -1 : f[i]);
    printf("%d\n", f[n] == 1e9 ? -1 : f[n]);
  }
  return 0;
}