// Arup Guha
// 12/6/2015
// Solution to Fall 2015 UCF HS Online Contest Problem: Wreck It!

import java.util.*;

public class wreck {

	public static int n;
	public static int k;
	public static boolean[][] adj;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=numCases; loop++) {

			// Read in the graph parameters.
			n = stdin.nextInt();
			int e = stdin.nextInt();
			k = stdin.nextInt();
			adj = new boolean[n][n];
			for (int i=0; i<e; i++) {
				int v1 = stdin.nextInt()-1;
				int v2 = stdin.nextInt()-1;
				adj[v1][v2] = true;
				adj[v2][v1] = true;
			}

			// Run a BFS and return the result - screen out easy no cases.
			if ((k == 0) || (k < n && bfs()))
				System.out.println("City #"+loop+": YES");
			else
				System.out.println("City #"+loop+": NO");
		}
	}

	public static boolean bfs() {

		// Set up BFS
		HashSet<Integer> used = new HashSet<Integer>();
		used.add(1);
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.offer(1);

		// Run it.
		while (q.size() > 0) {

			int state = q.poll();

			// Found a loop that's long enough.
			if (containsLoop(state)) return true;

			// Get the next possible states.
			ArrayList<Integer> next = getNext(state);

			// Put these in the queue.
			for (int i=0; i<next.size(); i++)
				if (!used.contains(next.get(i)))
					q.offer(next.get(i));
		}

		return false;
	}

	public static boolean containsLoop(int state) {

		int[] arr = toArray(state);

		// Check only for loops with item added last.
		for (int i=1; i<arr.length; i++)
			if (arr[i] == arr[0] && i > k)
				return true;

		return false;
	}

	public static int[] toArray(int state) {

		// Storing previous locations in three bits a piece - so peel them off.
		int[] res = new int[6];
		for (int i=0; i<6; i++) {
			res[i] = state & 7;
			state = state >> 3;
		}
		return res;
	}

	public static ArrayList<Integer> getNext(int state) {

		// Where I will store answers.
		ArrayList<Integer> next = new ArrayList<Integer>();

		// Where I am.
		int cur = (state & 7) - 1;

		// Left shifting and getting rid of most significant 3 bits to keep state size the same.
		int newframe = (state << 3) &0x3ffff;

		// Store the new potential state as an array.
		int[] states = toArray(newframe);

		// Add each item that is adjacent to cur, that is valid.
		for (int i=0; i<n; i++)
			if (adj[cur][i] && valid(states, i+1))
				next.add(newframe+i+1);

		return next;
	}

	public static boolean valid(int[] states, int next) {

		// See if cycle with this term comes too quickly.
		for (int i=2; i<6; i++)
			if (states[i] == next && i <= k)
				return false;

		// If not, we're good!
		return true;
	}
}