#include <stdio.h>
int max;
int n;
int map[21][21] = { { 0, }, };
void cal(int len, int arr[], int current) {//길이, 배열
int length = len + 1;
arr[current] = 1;
if (length > max)
max = length;
for (int i = 1; i <= n; i++) {
if (map[current][i] == 1 && arr[i] == 0) { //연결되어있고 방문한 길이 아니면
cal(length, arr, i);
}
}
arr[current] = 0;
}
int main(void) {
int test_case;
scanf("%d\n", &test_case);
for (int z = 1; z <= test_case; z++) {
int m;
scanf("%d%d", &n,&m);
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x,&y);
map[x][y] = 1;
map[y][x] = 1;//연결된 애들 체크
}
max = 0;
int arr[11] = { 0, };//이미 간길 체크
for (int i = 1; i <= n; i++) {
cal(0, arr, i);
}
printf("#%d %d\n", z,max);
for (int i = 0; i < 21; i++) {
for (int j = 0; j < 21; j++) {
map[i][j] = 0;
}
}
}
}