XYI - XYI

You are quite new to Bioinformatics studies. While working in the lab you have met Professor Shakil, who is a bit crazy. You know that there are twenty-two chromosomes and there is the X chromosome and the Y chromosome.

Now Professor Shakil is very determined that there are mutants hiding among us (After watching the new Wolverine movie he went nuts). And he is very positive about a new type of chromosome, which is the I chromosome.

As the Professor is very excited and not suitable for lab work, he will give you a chromosome each time. You have to determine which type it is (X, Y, I or NotValid).

Chromosomes can be viewed as a set of nodes and edges. Look at the images for details. The dotted line represents that there can be an arbitrary number of nodes and edges in these directions (they have to represent a straight line, though).

XIY

Input

In the first line, you will be given the number of test cases T, where T <= 200. Then the test cases will follow. Each test case will have two integers at the beginning, N and M. Here N is the number of nodes and M is the number of edges, where 4 <= N <= 500 and 3 <= M <= (N * N - 1) / 2. Then M lines will follow, each consisting of two integers, U and V, which specifies that there is an edge between node U and node V. It is guaranteed that and given graph will be connected and there will be at most one edge between two nodes.

Output

You have to output the correct chromosome each test case represents, or NotValid if the test case doesn’t represent the three given chromosomes. You have to print “Case T: Z”, (without the braces) for each test case, where T is the test case number and Z is the correct chromosome or “NotValid”. Please look at the sample I/O for details.

Sample

Input:
2
4 4
1 2
2 3
3 4
4 1
4 3
1 2
2 3
2 4

Output:
Case 1: NotValid
Case 2: Y

Problem Setter: Nafis Ahmed, Special Thanks: Nafis Sadique


Added by:Faiyaz
Date:2013-12-29
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2024-04-02 00:15:57
extra LF before each test case.
2017-11-20 13:10:33
Thanks for heads up Alexandre. Malformed input aside, nice problem.
2014-03-10 22:57:54 Alexandre Henrique Afonso Campos
@Sourabh Bansal
You have submitted only one solution for this problem and it was in C++. Whether you used cin or scanf, C++ doesn't care if in the input there are multiple \n gathered or spaces, so, your comment doesn't make any sense. Try to solve the tutorial problem http://www.spoj.com/problems/FSTCHAR/ and you will see how this kind of detail can make you get WA.
2014-03-02 21:49:28 Sourabh Bansal
for me only one \n was enough...
2014-01-08 12:19:43 Alexandre Henrique Afonso Campos
Good problem. Warning to Python (and others) users: there's more \n than the statement says.
2014-01-07 15:09:20 fitcat
As N >= 5 and M >= 4, the 2 test cases in the sample are invalid.

Reply: Constraints are updated.

Last edit: 2014-01-07 15:09:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.