文理学院程序设计在线练习


小明的排名

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 31   Accepted Submission(s): 10
Problem Description

考试成绩的好坏将对小明的零花钱有很大的影响。大明非常关注小明的考试排名,每次考试后总是询问老师小明的考试排名。

不过,这一次大明换了一种新的方法。大明随机地找了一些小明的同学,询问他们关于这次考试成绩的情况。当然这些同学也未必了解全部的考试信息,但根据他们掌握信息,可以给大明提供若干同学之间的成绩高低的关系。

比如,张三同学知道李四的成绩要比王五好,王五同学知道小明的成绩要比张三好,而李四同学知道李四的成绩要比张三好。
假设全班共有10人,根据上述信息,大明可以得到小明这次考试的最好成绩可能是第2名,这次考试的最坏成绩可能是第9名。因为根据掌握的信息,成绩高于小明的除了李四外,其他是否还有同学的成绩高于小明未知,因此理想状态下小明可能是第2名;类似地,成绩低于小明的除了张三外,其他是否还有同学的成绩低于小明未知,因此最坏情况下小明可能是第9名。

假设小明所在的班级一共有n个学生,小明的学号是1号,给定若干同学之间的成绩关系,假设不会出现并列的情况,请你确定小明的可能的最好名次。若给出的成绩关系有矛盾,输出:sorry。否则输出小明的可能的最好名次。

Input

输入数据首先包含一个整数T(1<=T<=20),表示测试实例的个数,然后是T组测试数据。
每组测试的第一行是2个整数N, M(2<=N<=50,1<=M<=100),分别代表学生总数和关系总数。
然后是 M 行数据,每行的2个整数x y,表示学号为x的学生成绩高于学号为y的学生成绩。

Output

对于每组测试,若给出的成绩关系有矛盾,输出sorry;否则,输出小明的可能的最好名次。

Sample Input
4
4 5
2 1
3 1
3 2
4 3
4 2
3 2
2 1
1 2
26 1
26 1
10 3
2 3
3 2
1 2
Sample Output
4
sorry
2
sorry
Author

flx

Source

usx第六届程序设计竞赛