#include <stdio.h>
#include <string.h>

#define NMAX 1001

int g[NMAX][NMAX], custo[NMAX], fila[NMAX];

int main() {
	int n, m;
	int ntestes, teste;
	int x, y;
	int i, j;
	int v;
	int ini, fim;

	scanf("%d", &ntestes);

	for (teste=1; teste<=ntestes; teste++) {
		if (teste!=1) {
			printf("\n");
		}
		scanf("%d %d", &n, &m);
		memset(g, 0, sizeof(g));
		memset(custo, 0, sizeof(custo));
		for (i=0; i<m; i++) {
			scanf("%d %d", &x, &y);
			g[x][y]=1;
			g[y][x]=1;
		}
		ini=0;
		fim=0;
		fila[fim++]=0;
		while (ini!=fim) {
			v=fila[ini++];
			for (i=1; i<n; i++) {
				if (g[v][i]&&!custo[i]) {
					custo[i]=custo[v]+1;
					fila[fim++]=i;
				}
			}
		}
		for (i=1; i<n; i++) {
			printf("%d\n", custo[i]);
		}
	}

	return 0;
}