#include <bits/stdc++.h>

typedef long long LL;

#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; ++i)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; --i)

template <typename Tp> void in(Tp &x) {
  char ch = getchar(), f = 1; x = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}

template <typename Tp> bool chkmax(Tp &x, Tp y) {return x >= y ? 0 : (x=y, 1);}
template <typename Tp> bool chkmin(Tp &x, Tp y) {return x <= y ? 0 : (x=y, 1);}
template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}

const int MAXN = 100010;

int T, n, m, K;
int f[MAXN];

void solve() {
  in(n); in(m); in(K);
  FOR(i, 1, n) f[i] = 0x3f3f3f3f; f[K] = 0;
  FOR(i, 1, m) {
    int x, y; in(x); in(y);
    int preX = f[x], preY = f[y];
    f[x] = Min(f[x] + 1, preY);
    f[y] = Min(f[y] + 1, preX);
  }
  FOR(i, 1, n) {
    if (f[i] != 0x3f3f3f3f)
      printf("%d", f[i]);
    else printf("-1");
    if (i != n) printf(" ");
  }
  putchar(10);
}

int main() {
  in(T); while (T--) solve();
  return 0;
}