Professor John

https://acs.jxnu.edu.cn/problem/NOIOPJCH03083529

描述：

Professor John is investigating a math problem. He has obtained some relations among several variables. Now he would like to know if there are any other relations that can be deduced from these obtained ones. For example, the known relations are given as follows: A < B, C > B and C < D, other relations including A < C, A < D and B < D can be deduced. Since he has been working for too long, Professor John decides to grant himself a vacation while assigning you to do the job. Are you ready?

John教授正在研究一个数学问题。他有一些变量的关系。现在他想知道是否有能从这些已拥有的关系中推断出来的其他关系。例如，已知以下关系：a<b,c>b c<d,其他能被推断出的关系包括a<c,a<d,b<d。因为他工作时间太长了，john教授决定把这些工作分配给你而自己去度假了。你准备好了吗。

输入：

The first line of input contains an integer N, which is the number of test cases. Then N test cases follow. For each test case: the 1st line contains a positive integer m (<= 100) which is the number of given relations; the following m lines each contains a given relation, in the format Variable1 < Variable2 or Variable1 > Variable2
A "Variable" is represented by a capital character. There will not be conflicting relations given.

第一行包含一个整数N，测试样例的数量。然后跟着n个测试样例。对于每个样例，第一行包含一个正整数m代表要给出关系的数量。接下来的m行每行包含一个关系，以V1<V2或V1>V2的形式

一个变量由一个大写字母表示。不会给出矛盾的关系

输出：

For each test case, first print in one line "Case d:" where d is the number of the test case, start counting from 1. Then output all the relations which can be deduced from the given relations in alphabetical order, in the format Variable1 < Variable2. Each relation occupies one line. No extra space shall be printed. The given relations must NOT be included. If no new relation is found, output "NONE" in one line.

对于每一个测试样例，先输出一行“case d：”，d是测试样例号，从1开始算。然后以字典序输出所有能被推断出来的关系，以V1<V2的形式，每一个关系占一行。没有额外的空格。给定的关系不能包含在内。如果没有新关系，输出一行NONE