test

#include <iostream>

using namespace std;

int n, m;

int a[50][50];
int start, endd;

int queue[10000000];
int front, rear;
int visit[50];
int res[50];
int check[50];
int ans;
int road[50];
void resetvisit() {
	for (int i = 1; i <= n; i++) {
		visit[i] = 0;
		check[i] = 0;
	}
	
}



void backtrack(int x, int count) {
	
	for (int i = 1; i <= n; i++) {
		
		
		
		if (a[x][i] == 1 && check[i] == 0) {
			cout << x << "--->" <<  i << " " << count <<  endl;
			
			check[i] = 1;
			backtrack(i, count + 1);
			check[i] = 0;
			
			
		}
		
	}
}

void solve(int testcase) {
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
	}
	
	
	for (int i = 1; i <= n; i++) {
		check[i] = 0;
	}
	ans = 99999;
	resetvisit();
	start = 1;
	endd = 2;
	check[start] = 1;
	backtrack(start, 0);
	start = 2;
	endd = 1;
	resetvisit();
	check[start] = 1;
	backtrack(start, 0);
	for (int i = 1; i <= n; i++) {
		cout << res[i] << " ";
	}
	cout << endl;
}
int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}