/* 二分图 题目给出的是确定不连通的边 如果我们拿剩下的可能联通也可能不连通的边跑最大匹配 如果不是完美非配 也就是说把所有可能的边都认为是一定的 这样都跑不出来（不能匹配到每个点）那么一定不能确定任何一组 如果是完美匹配 就说明可能有能肯定的组合 接下来我们一条一条的删边 如果删完之后跑出来的不是完美匹配那么这一条边就是肯定的 最后记一下答案 拍一下序 输出就好了 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 210 using namespace std; int n,num,head[maxn],g[maxn][maxn],ans,f[maxn],match[maxn],sum,ei; struct Ans { int x,y; }an[maxn*maxn]; struct node { int u,v,pre; }e[maxn*maxn]; int cmp(const Ans &a,const Ans &b) { return a.x<b.x; } int init() { int x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Add(int from,int to) { num++; e[num].u=from; e[num].v=to; e[num].pre=head[from]; head[from]=num; } int Dfs(int k) { for(int i=head[k];i;i=e[i].pre) if(f[e[i].v]==0&&i!=ei) { f[e[i].v]=1; if(match[e[i].v]==0||Dfs(match[e[i].v])) { match[e[i].v]=k; return 1; } } return 0; } int main() { n=init(); int u,v; while(1) { u=init();v=init(); if(u==0&&v==0)break; g[u][v]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(g[i][j]==0)Add(i,j); for(int i=1;i<=n;i++) { memset(f,0,sizeof(f)); ans+=Dfs(i); } if(ans!=n) { printf("none "); return 0; } for(int i=1;i<=num;i++) { memset(match,0,sizeof(match)); ans=0; for(int j=1;j<=n;j++) { memset(f,0,sizeof(f)); ei=i; ans+=Dfs(j); } if(ans!=n) { sum++; an[sum].x=e[i].u; an[sum].y=e[i].v; } } if(sum==0) { printf("none "); return 0; } sort(an+1,an+1+sum,cmp); for(int i=1;i<=sum;i++) printf("%d %d ",an[i].x,an[i].y); return 0; }