Deja Vu

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The following is an easy game that the setter of this problem played when he was 8:
A boatman, a wolf, a sheep, and a cabbage are on the bank of a river. They have a small boat that is capable of carrying the boatman and at most one other animal/item with him. However, if left alone by the boatman, the wolf can eat the sheep, and the sheep can eat the cabbage. How can all four be moved safely to the opposite bank of the river?
Here is a nice visualization of the whole process in the original game. Disclaimer: writers, testers and CodeChef are not related to this link.
This leads to a more general problem. If there are other groups of animals/items with the boatman, and if the boat is big enough to seat at most K animals/items other than the boatman, how quickly can all of them be moved to the opposite bank of the river in such a way that nobody/nothing gets eaten?
We will give you the number of animals/items (not including the boatman). We will also give you the new capacity of the boat. Moreover, we will give you all a list of pairs of the form "X Y" where the Xth animal/item will be eaten by the Yth one if they are both on the opposite bank to the boatman.
Assuming a valid solution exists, you are to determine the minimum number of boat trips across the river to achieve the task.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test contains three space separated integers N, M and K  the number of animals/items not including the boatman, the number of relations of the form "X will be eaten by Y", and the capacity of the boat (not including the boatman), respectively.
The following M lines contain pairs of the form X Y with the meaning that the Xth animal/item will be eaten by the Yth one if they are both on the opposite bank to the boatman.
Output
For each test case, output a single line containing a single integer  the minimum number of boat trips across the river necessary. In the test cases it is always possible to accomplish this goal.
Constraints
 1 ≤ T ≤ 20
 1 ≤ K ≤ N
 Subtask 1: 1 ≤ N ≤ 3, 0 ≤ M ≤ 3  22 points.
 Subtask 2: 1 ≤ N ≤ 6, 0 ≤ M ≤ 15  34 points.
 Subtask 3: 1 ≤ N ≤ 13, 0 ≤ M ≤ 78  44 points.
Example
Input: 2 3 2 1 1 2 2 3 3 3 2 1 2 1 3 2 3 Output: 7 3
Explanation
The first example is the original version of the problem.
Author:  xcwgf666 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/WSCAGAIN 
Tags  bfs, easy, ltime18, xcwgf666 
Date Added:  14082014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 