【codevs1222】信与信封问题

2014年3月2日2,7460

题目描述 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 Description

n文件的第一行是一个整数n(n≤100)。信和信封依次编号为1,2,…,n。

n接下来的各行中每行有2个数i和j,表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0,表示结束。

输出描述 Output Description

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

样例输入 Sample Input

3

1  2

1  3

2  1

0  0

样例输出 Sample Output

1   1

题解

这是一道二分图匹配的变式,假如一条边不可获缺,那么没有它一定无法完美匹配,由此可以推得先进行一次匹配,再对匹配的边依次删除,如果不能完美匹配就输出