/*
 * Author: Kewth

 * Date:
  echo -n '  ' && date +%Y.%m.%d # Type "!!sh" in Vim.

 * Solution:
  To be updated after "Accept".

 * Digression:

 * CopyRight:
   __  __                  __   __
  |  |/  |.-----.--.--.--.|  |_|  |--.
  |     < |  -__|  |  |  ||   _|     |
  |__|\__||_____|________||____|__|__|

 */

#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
    inline operator int () { int x; return scanf("%d", &x), x; }
    /* inline operator ll () { ll x; return scanf("%lld", &x), x; } */
    /* template<class T> inline void operator () (T &x) { x = *this; } */
    /* template<class T, class ...A> inline void operator () (T &x, A &...a) */
    /* { x = *this; this -> operator () (a...); } */
} read;

const int maxn = 100005;
int a[maxn];

int main () {
    int q = read;
    while (q --) {
        int n = read, m = read, s = read;
        std::fill(a, a + n + 1, 1000000000);
        a[s] = 0;
        while (m --) {
            int x = read, y = read;
            int ax = std::min(a[x] + 1, a[y]);
            int ay = std::min(a[y] + 1, a[x]);
            a[x] = ax, a[y] = ay;
        }
        for (int i = 1; i <= n; i ++)
            printf("%d%c", a[i] == 1000000000 ? -1 : a[i], " \n"[i == n]);
    }
}