提示: 欢迎访问OurACM平台。
Problem 1202 信与信封问题

Accept: 246    Submit: 1342
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出。但是,第二天John的儿子Small John将这n封信都拿出了信封。不幸的是,Small John无法将拿出的信正确地装回信封中了。

编程任务

将Small John所提供的n封信依次编号为1,2,...,n; 且n个信封也依次编号为1,2,...,n。假定Small John能提供一组信息:第i封信肯定不是装在信封j中。请编程帮助Small John,尽可能多地将信正确地装回信封。

Input

本题有多组输入数据,你必须处理到EOF为止。
每组数据的第一行是一个整数n(n≤100)。信和信封依次编号为1,2,…,n。
接下来的各行中每行有2个数i和j,表示第i封信肯定不是装在第j个信封中。输入最后一行是2个0,表示结束。

Output

对于每组数据,输出的各行中每行有2个数i和j,表示第i封信肯定是装在第j个信封中。请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件,则输出“none”。
每组输出结束之后,输出一个空行。

Sample Input

3 1 2 1 3 2 1 0 0

Sample Output

1 1

Source

FJOI 2001

Submit  Back  Status  Discuss