SP17819 XYI - XYI

你刚开始接触生物信息学。在实验室里，你遇到了有点疯狂的 Shakil 教授。你知道，人类有 22 条常染色体，还有 X 和 Y 染色体。现在，Shakil 教授经过一番思考后，相信我们中间藏着变异者（看完新的《金刚狼》电影后他对这个想法特别执着）。他坚信存在一种全新的 I 染色体。 由于教授过于激动，不能亲自完成实验室工作，所以他会给你一些染色体例子，你需要判断这些染色体的类别是 X、Y、I 还是 NotValid（无效）。 染色体可以被视为一组节点和边构成的图。具体可以参考图示，虚线表示这些方向上可能存在任意数量的节点和边，但必须形成一条直线。 

第一行是测试用例的数量 $T$，满足 $1 \leq T \leq 200$。接下来是 $T$ 组测试用例。每个测试用例首先包含两个整数 $N$ 和 $M$，分别表示节点数和边数，其中 $4 \leq N \leq 500$ 且 $3 \leq M \leq \frac{N^2 - 1}{2}$。然后紧接着的 $M$ 行，每行包含两个整数 $U$ 和 $V$，表示节点 $U$ 和节点 $V$ 之间有一条边。保证所有的图都是连通的，且任意两个节点之间最多只有一条边。

对于每个测试用例，输出它代表的正确染色体类型，或者若不符合任何一种已知染色体，输出 `NotValid`。格式为 `Case T: Z`，其中 $T$ 是测试用例编号，$Z$ 是染色体类型或 `NotValid`。请参考示例的输入输出格式来完善你的答案。