/*
 * Calling me, calling you / IPSC 2007, solver
 * (c) Goober
 */

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

#define MAXN 100000
#define MAXM 100000

int n, m, k;
int start[MAXN+1];
typedef struct { int a, b; } PAIR;
PAIR calls[MAXM*2];
int done[MAXN+1];

int k12case(int v, int p)
{
	int tojoin[2];
	int joins = 0;
	int i;

	done[v] = 1;
	for (i = start[v-1]; i < start[v]; i++) if (!done[calls[i].b])
	{
		if (k12case(calls[i].b, v))
			tojoin[joins++] = calls[i].b;
		if (joins == k)
			while(joins > 0) 
				printf("%d %d\n", v, tojoin[--joins]);
	}
	if (joins == 0)
		return 1;
	printf("%d %d\n", v, tojoin[0]);
	if (p != 0)
		printf("%d %d\n", v, p);
	return 0;
}

int cmp(const void *XX, const void *YY)
{
	const PAIR *X = (const PAIR*)XX;
	const PAIR *Y = (const PAIR*)YY;
	if (X->a != Y->a)
		return X->a - Y->a;
	return X->b - Y->b;
}

int best;
int candidate[MAXN+1], prev[MAXN+1];
PAIR conn[MAXM], bestconn[MAXM];
int conns, bestconns;
int todo;

void connect(int v, int u)
{
	int i;
	done[u]++;
	for (i=start[u-1]; i<start[u]; i++)
		if (!candidate[calls[i].b]++)
			prev[calls[i].b] = u;
	conn[conns].a=v;
	conn[conns].b=u;
	conns++;
	todo--;
}

void disconnect(int v, int u)
{
	int i;
	for (i=start[u-1]; i<start[u]; i++)
		candidate[calls[i].b]--;
	done[u]--;
	conns--;
	todo++;
}

void try1(int cnt);

void tryconnect(int cnt, int v, int frees, int first)
{
	int i;
	
	if (frees > 0)
	{
		for (i=start[v-1] + first; i < start[v]; i++)
		{
			int u;
			u = calls[i].b;
			if (done[u])
				continue;
			connect(v,u);
			if (frees > 0)
				tryconnect(cnt, v, frees-1, first+1);
			disconnect(v,u);
		}
	}
	try1(cnt);
}

void try1(int cnt)
{
	int i;
	if (cnt >= best)
		return;
	if (todo == 0)
	{
		best = cnt;
		memcpy(bestconn, conn, sizeof(bestconn));
		bestconns = conns;
		return;
	}

// First, we try to buy more Happy Packs for those already having them
	for (i=1; i<=n; i++) if (done[i])
		tryconnect(cnt+1, i, k, 0);
	else if (candidate[i])
	{
		done[i]++;
		connect(i, prev[i]);
		tryconnect(cnt+1, i, k-1, 0);
		disconnect(i, prev[i]);
		done[i]--;
	}
}

int bigcase()
{
	int i;
	best = n/2;
	for (i=1; i<=n; i++)
		candidate[i] = 0;
	conns=0;
	todo=n;
	connect(0, 1);
	try1(0);
	disconnect(0, 1);
	if (best < n/2)
	{
		for (i=1; i<bestconns; i++)
			printf("%d %d\n", bestconn[i].a, bestconn[i].b);
		return 1;
	}
	else
	{
		k = 2;
		return 0;
	}
}

int main()
{
	int t, i, a, b;

	scanf("%d", &t);
	while(t--)
	{
		scanf("%d %d %d", &n, &m, &k);
		for (i=1; i<=n; i++)
			start[i] = 0;
		for (i=0; i<m; i++)
		{
			scanf("%d %d", &a, &b);
			calls[2*i].a = a;
			calls[2*i].b = b;
			start[a]++;
			calls[2*i+1].a = b;
			calls[2*i+1].b = a;
			start[b]++;
		}
		start[0] = 0;
		for (i=1; i<=n; i++) start[i] += start[i-1];
		qsort(calls, 2*m, sizeof(PAIR), cmp);

		for (i=1; i<=n; i++)
			done[i] = 0;
		if (k <= 2 || !bigcase())
			k12case(1, 0);
		printf("0 0\n");
	}
	return 0;
}