407534: GYM102823 C Binary Tree

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Binary Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is a binary tree with $$$N$$$ nodes.

As a tree killer, you picked subtrees from that tree yesterday!

And now you regret.

You probably remember the height of $$$M$$$ subtrees with distinct roots, but can you reconstruct that tree?

Well, that may be hard for you because of the tremendous number of nodes.

You just have to check whether you can!

By the way, guess whether original tree is a complete binary tree as well!

Input

The first line of the input file contains a simple integer $$$T$$$ ($$$1\le T\le 100$$$) describing the number of test cases.

Then there are $$$2 \times T$$$ lines with every two lines representing a test case.

The first line of the test case contains two integers $$$N$$$, $$$M$$$ ($$$1\le N\le 10^9$$$, $$$1\le M\le 10^5$$$) described above.

The second line of that contains $$$M$$$ numbers representing the heights ranging in $$$[1,10^9]$$$.

Output

Please print $$$T$$$ lines exactly, with the answer to corresponding test case each line.

For each answer, print Case $$$d$$$: ($$$d$$$ represents the order of test case) first, and then write your answer:

if what you remember cannot form a binary tree, print INVALID;

if it may be binary tree, then just check whether it may be a complete binary tree: IMPOSSIBLE (it must not be a complete binary tree), POSSIBLE (it may be a complete binary tree), DEFINITELY (it must be a complete binary tree).

ExampleInput
5
1 1
1
1 1
2
2 1
2
2 2
1 2
15 3
3 3 3
Output
Case 1: DEFINITELY
Case 2: INVALID
Case 3: POSSIBLE
Case 4: POSSIBLE
Case 5: IMPOSSIBLE

加入题单

上一题 下一题 算法标签: