import java.util.*;
public class Solution {
	static int answer;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int a=1;a<=t;a++) {
        	answer=0;
        	int n=sc.nextInt();
        	int m=sc.nextInt();
        	boolean[][]map=new boolean[n+1][n+1];
        	for(int b=0;b<m;b++) {
        		int x=sc.nextInt();
        		int y=sc.nextInt();
        		map[x][y]=true;
        		map[y][x]=true;
        	}
        	for(int b=1;b<=n;b++) {
        		boolean[]visited=new boolean[n+1];
        		dfs(b,visited,n,map);
        	}
            System.out.println("#"+a+" "+answer);
        }
        sc.close();
	}

	private static void dfs(int z, boolean[] visited, int n, boolean[][] map) {
		boolean[]newvisited=new boolean[n+1];
    	for(int a=1;a<=n;a++) {
    		newvisited[a]=visited[a];
    	}
    	newvisited[z]=true;
    	int count=0;
    	for(int a=1;a<=n;a++) {
    		if(newvisited[a]) {
    			count++;
    		}
    	}
    	answer=Math.max(answer, count);
    	for(int a=1;a<=n;a++) {
    		if(map[z][a]&&!newvisited[a]) {
    			dfs(a,newvisited,n,map);
    		}
    	}
	}
}