#include<iostream>
using namespace std;
#include<stdlib.h>
struct point1
{
	int d;
	point1 *next;
};

point1 map[20001];
int visit[20001];
int min,node,t,n,m;

int dfs(int i,int j)
{
	point1 *p;
	p=map[j].next;
	while(p!=NULL)
	{
		if(p->d!=i&&visit[p->d]==0)
		{
			visit[p->d]=1;
			m++;
			dfs(i,p->d);
		}
		p=p->next;
	}
	return m;
}
main()
{
	int i,j,a,b,max;
	point1 *p,*p2;
	cin>>t>>n;
	for(i=1;i<=n;i++)
	{
		map[i].next=NULL;
	}
	while((t--)!=0)
	{
		max=0;
		memset(visit,0,sizeof(visit));
		memset(map,0,sizeof(map));
		for(i=1;i<n;i++)
		{
			cin>>a>>b;
			p=(point1*)calloc(1,sizeof(point1));
			p->d=b;
			p->next=NULL;
			if(map[a].next!=NULL)
				p->next=map[a].next;
			map[a].next=p;
	        
			p=(point1*)calloc(1,sizeof(point1));
			p->d=a;
			p->next=NULL;
			if(map[b].next!=NULL)
				p->next=map[b].next;
			map[b].next=p;		
		}
		min=200001;
		for(i=1;i<=n;i++)
		{
			memset(visit,0,sizeof(visit));
			max=m=0;
			for(j=1;j<=n;j++)
			{
				if(j!=i&&visit[j]==0)
				{
					m=0;
					dfs(i,j);
				}
			     if(m>max)
					 max=m;
			}
			if(max<min)
			{
				min=max;
				node=i;
			}
		}
		cout<<node<<" "<<min<<endl;

	for(i=1;i<=n;i++)
	{
		p =map[i].next;
		while (p != NULL)
		{
			p2 = p;
			p = p->next;
			free(p2);
		}
		map[i].next=NULL;
	}
	}
	return 0;
}