#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define clr(x) memset((x), 0, sizeof(x))
#define pb push_back
#define mp make_pair
#define sz size()
#define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
#define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
#define forn(i, n) for(int i=0; i<(int)(n); i++)
#define ford(i, n) for(int i=(n)-1; i>=0; i--)
#define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)

template <class _T> inline _T sqr(const _T& x) { return x * x; }
template <class _T> inline string tostr(const _T& a) { ostringstream os(""); os << a; return os.str(); }

typedef long double ld;

// Constants
const ld PI = 3.1415926535897932384626433832795;
const ld EPS = 1e-11;

// Types
typedef long long i64;
typedef set < int > SI;
typedef vector < int > VI;
typedef map < string, int > MSI;
typedef pair < int, int > PII;

const int MAXN = 16;
const int MAXM = 102400;

int n, m, k;
int a[MAXN][MAXN * 2 + 1];
int b[MAXN][MAXN];
int e[MAXM * 2][4];
bool c[1 << MAXN];
bool d[MAXN + 1][1 << MAXN];
int pa[MAXN + 1][1 << MAXN];
int tt;
int tin[MAXN];
int tup[MAXN];
int col[MAXN];
int u[MAXN];
set < PII > ans;

bool dfs1(int k, int prev, int mask)
{
	u[k] = true;
	tin[k] = tup[k] = tt++;
	For(i1, 1, a[k][0])
	{
		int i = a[k][i1];
		int v = e[i][1];
		if (!(mask & (1 << v))) continue;
		if (!u[v])
		{
			if (dfs1(v, i, mask)) return true;
			if (tup[v] > tin[k]) return true;
			if (tup[k] > tup[v]) tup[k] = tup[v];
		}
		else if (i != (prev ^ 1))
		{
			if (tup[k] > tin[v]) tup[k] = tin[v];
		}
	}
	return false;
}

void dfs2(int k, int prev, int mask)
{
	u[k] = 1;
	For(i1, 1, a[k][0])
	{
		int i = a[k][i1];
		int v = e[i][1];
		if (!(mask & (1 << v))) continue;
		if (!u[v])
		{
			e[i][2] = k;
			e[i][3] = v;
			e[i ^ 1][2] = k;
			e[i ^ 1][3] = v;
			dfs2(v, i, mask);
		}
		else if (i != (prev ^ 1) && u[v] == 1)
		{
			e[i][2] = k;
			e[i][3] = v;
			e[i ^ 1][2] = k;
			e[i ^ 1][3] = v;
		}
	}
	u[k] = 2;
}

bool check(int mask)
{
	clr(u);
	int cnt = 0;
	tt = 0;
	forn(i, n)
	{
		if (mask & (1 << i))
		{
			if (!u[i])
			{
				if (++cnt > 1) return false;
				if (dfs1(i, -1, mask)) return false;
			}
		}
	}
	return cnt == 1;
}

int main()
{
#ifdef ROOM_311
	time_t et_0 = clock();
#endif
	cout << setiosflags(ios::fixed) << setprecision(10);

	int z = 0;
	scanf("%d%d%d", &n, &m, &k);
	memset(e, 0xff, sizeof(e));
	clr(a);
	clr(b);
	forn(i, m)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x--;
		y--;
		b[x][y]++;
		b[y][x]++;

		e[z][0] = x;
		e[z][1] = y;
		if (b[x][y] <= 2) a[x][++a[x][0]] = z;
		z++;
		e[z][0] = y;
		e[z][1] = x;
		if (b[y][x] <= 2) a[y][++a[y][0]] = z;
		z++;
	}
	forn(i, 1 << n)
	{
		c[i] = check(i);
	}
	clr(d);
	d[0][0] = true;
	forn(i, k)
	{
		forn(mask, 1 << n)
		{
			if (!d[i][mask]) continue;
			int y = ((1 << n) - 1) ^ mask;
			for(int x = y; x; x = (x - 1) & y)
			{
				if (c[x])
				{
					d[i + 1][mask ^ x] = true;
					pa[i + 1][mask ^ x] = mask;
				}
			}
		}
	}
	if (d[k][(1 << n) - 1])
	{
		puts("YES");
		int mask = (1 << n) - 1;
		clr(u);
		Ford(i, k, 1)
		{
			int x = pa[i][mask] ^ mask;
			forn(j, n)
			{
				if (x & (1 << j))
				{
					col[j] = i - 1;
				}
			}
			forn(j, n)
			{
				if (col[j] == i - 1)
				{
					dfs2(j, -1, x);
					break;
				}
			}
			mask = pa[i][mask];
		}
		forn(i, m * 2)
		{
			if (e[i][2] != -1)
			{
				ans.insert(mp(e[i][2], e[i][3]));
			}
		}
		forn(i, m * 2)
		{
			if (e[i][2] == -1)
			{
				if (col[e[i][0]] == col[e[i][1]])
				{
					PII t = mp(e[i][0], e[i][1]);
					if (ans.count(t))
					{
						e[i][2] = e[i][0];
						e[i][3] = e[i][1];
					}
					else
					{
						t = mp(e[i][1], e[i][0]);
						if (!ans.count(t))
						{
							fprintf(stderr, "Botwa !!!\n");
							return 0;
						}
						e[i][2] = e[i][1];
						e[i][3] = e[i][0];
					}
				}
				else
				{
					e[i][2] = e[i][0];
					e[i][3] = e[i][1];
					if (col[e[i][0]] > col[e[i][1]]) swap(e[i][2], e[i][3]);
				}
			}
		}
		forn(i, m)
		{
			printf("%d %d\n", e[i * 2][2] + 1, e[i * 2][3] + 1);
		}
	}
	else
	{
		puts("NO");
	}

#ifdef ROOM_311
	time_t et_1 = clock();
	fprintf(stderr, "Execution time = %0.0lf ms\n", (et_1 - et_0) * 1000.0 / CLOCKS_PER_SEC);
#endif
	return 0;
}