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


小明的最爱

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

Total Submission(s): 61   Accepted Submission(s): 29
Problem Description

小明有许多爱好,比如:打乒乓球,看电视,听音乐、看书、踢足球等等。

同时,我们还假设爱好的优先程度是具有传递性的,也就是说:如果爱好A优先于爱好B,而爱好B又优先于爱好C,那么爱好A就优先于爱好C。

可是有时候因条件的限制,并不是所有的爱好都可以满足。比如:
若是下雨天,踢足球就无法实现。只能在打乒乓球,看电视,听音乐、看书之间选择它的最爱。
若是只有一个人,踢足球和打乒乓球也只能放弃。只能在看电视,听音乐、看书之间选择它的最爱。
若是希望锻炼身体。就只能在踢足球和打乒乓球之间进行选择。

由于爱好太多,小明自己也经常忘记不同爱好之间的优先等级,因此为了方便,小明曾经在纸上完整地记录下他的全部爱好之间的关系,可是小明最近不小心把那张纸弄丢了。幸亏老明曾经看到过那张纸,凭借记忆,老明还能正确地记得其中的部分内容。

重要说明:小明记录在纸上的不同爱好之间的优先程度不会出现矛盾的情况,这也就可以保证两种不同的爱好之间最多只存在一种优先程度.而不会出现爱好A优先于爱好B,而爱好B又优先于爱好A的情况,不管是直接关系还是间接关系。例如: A优先于B,B优先于C,C优先于A,这就是一种矛盾的情况,因为A优先于爱好B,而爱好B又间接通过C优先于爱好A.

现在,请你根据老明提供的信息,帮助小明迅速地在给定的2个爱好之间做出抉择,也就是请你回答:小明更喜爱哪个爱好?

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。
对于每组测试,第一行是3个整数n,m,k. (2<=n<=80,1<=m<=n*(n-1)/2,1<=k<=80), 表示共有n种不同的爱好,不同的爱好用数字1~n表示。后面的m行就是老明提供的信息,每行2个整数x,y (1<= x,y <=n), 代表爱好x优先于爱好y,然后是k行提问,每行2个整数A B,数据之间用空格分隔,且A<>B,请你依次回答A和B之间,小明更喜爱哪个?

Output

对于每个提问,若能比较,输出小明相对更喜欢的那个爱好。若无法比较,请输出"Sorry"。

Sample Input
3
3 2 2
1 2
2 3
1 3
3 2
3 1 2
1 3
1 3
3 2
5 5 4
1 4
1 2
3 2
2 5
4 5
2 3
3 1
5 1
4 3
Sample Output
1
2
1
Sorry
3
Sorry
1
Sorry
Author

flx

Source

usx第四届程序设计竞赛