Baking Cupcakes

Problem code: MUFFINS

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 n-1. 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 n-g ≤ 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

Date: 2010-08-09
Time limit: 3

s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

guys i am done with code it

akash1110 @ 21 Aug 2010 10:15 PM

guys i am done with code

it was compiles in turbo c++

but codechef app isnt acceptin syntax from dt format pls help me out fast

what is cupcake baking tin ?

iman_movahedi @ 21 Aug 2010 11:41 PM

what is cupcake baking tin ?

@iman: A cupcake baking tin

david_adm @ 21 Aug 2010 11:48 PM

@iman: A cupcake baking tin is a large piece of metal with a number of round indentations that can hold batter.  When filled with batter and placed in an appropriately hot oven for an appropriate amount of time, a delicious treat emerges, which is cooled and often covered with frosting before serving (and makes a far better treat than muffins).

Nice problem, learnt

flying_ant @ 21 Aug 2010 11:58 PM

Nice problem, learnt something new - how  cupcakes is baked :) .

Does the problem not reduce

rahulakaneo @ 22 Aug 2010 12:17 AM

Does the problem not reduce to finding an independent set of size at least G?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions