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).
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
hide comments
leoweyles:
2024-04-02 00:15:57
extra LF before each test case. |
|
nadstratosfer:
2017-11-20 13:10:33
Thanks for heads up Alexandre. Malformed input aside, nice problem. |
|
Alexandre Henrique Afonso Campos:
2014-03-10 22:57:54
@Sourabh Bansal
|
|
Sourabh Bansal:
2014-03-02 21:49:28
for me only one \n was enough... |
|
Alexandre Henrique Afonso Campos:
2014-01-08 12:19:43
Good problem. Warning to Python (and others) users: there's more \n than the statement says. |
|
fitcat:
2014-01-07 15:09:20
As N >= 5 and M >= 4, the 2 test cases in the sample are invalid.
|
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 |