题目描述 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
/*
匈牙利算法的变形
具体做法：
将原来给每一封信匹配的信封删除，看这封信能不能匹配别的信封
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define M 110
using namespace std;
int used[M],belong[M],a[M][M],be2[M],n;
int find(int i)
{
for(int j=;j<=n;j++)
if(!used[j]&&a[i][j])
{
used[j]=;
if(!belong[j]||find(belong[j]))
{
belong[j]=i;
return ;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
a[i][j]=;
while()
{
int x,y;
scanf("%d%d",&x,&y);
if(x==&&y==)break;
a[x][y]=;
}
int tot=;
for(int i=;i<=n;i++)
if(find(i))
{
memset(used,,sizeof(used));
tot++;
}
if(tot<n)
{
printf("none");
return ;
}
for(int i=;i<=n;i++)be2[belong[i]]=i;
int flag=;
for(int i=;i<=n;i++)
{
memset(used,,sizeof(used));
a[i][be2[i]]=;
belong[be2[i]]=;
if(!find(i))
{
printf("%d %d\n",i,be2[i]);
flag=;
}
a[i][be2[i]]=;
belong[be2[i]]=i;
}
if(!flag)printf("none");
return ;
}