Baking Cupcakes

All submissions for this problem are available.
The Chef is planning on serving cupcakes for dessert. However, time is running out and the Chef has only enough time to bake one batch. Thankfully, the cupcake baking tin the Chef plans on using has barely enough spaces to ensure each guest receives one cupcake.
To the Chef's dismay, some of the spaces in the cupcake tin are too close to each other. If cupcake batter is placed in two such spaces then they will bake together and neither will have the aesthetically pleasing round shape one expects from gourmet cupcakes.
The Chef wants to impress his guests with this dessert, so he wants all cupcakes to be perfectly round. You must determine if it is possible for the desired number of cupcakes to be baked without any two baking in to each other.
Input
The first line consists of a single integer T ≤ 30 denoting the number of test cases to follow. Each test case begins with a single line consisting of three integers n,m, and g. Here, n is the number of spaces in the cupcake tin, m is the number of conflicting pairs of spaces in the tin, and g is the number of guests. Following this line is m lines describing the conflicting pairs. Each line consists of two distinct integers i and j, both between 0 and n1. This means spaces i and j are conflicting so batter may only be placed in at most one of them.
The bounds are 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 20,000, and 0 ≤ g ≤ n. Since the cupcake tin has barely more spaces than guests (if any), then we also have ng ≤ 15.
Output
The output for each test case consists of a single line containing "Possible" if the Chef can bake all cupcakes perfectly round or "Impossible" if the Chef must settle for some cupcakes being imperfect.
Example
Input: 2 3 2 2 0 1 1 2 3 3 2 0 1 1 2 2 0 Output: Possible Impossible
Author:  friggstad 
Tester:  pieguy 
Editorial  http://discuss.codechef.com/problems/MUFFINS 
Tags  cook02, friggstad, hard 
Date Added:  9082010 
Time Limit:  0.619048 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, 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. 