http://codeforces.com/gym/101755/problem/F
#include <iostream> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <cstdio> #include <set> #include <map> #include <stack> //#include <tr1/unordered_map> //#include <unordered_map> #include <cmath> //#include<bits/stdc++.h> using namespace std; #define sfi(i) scanf("%d",&i) //#define sfl(i) scanf("%I64d",&i) #define sfs(i) scanf("%s",(i)) #define pri(i) printf("%d\n",i) #define prl(i) printf("%I64d\n",i) #define sff(i) scanf("%lf",&i) #define ll long long #define ull unsigned long long #define uint unsigned int #define mem(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f #define inf 8e19 #define eps 1e-10 #define PI acos(-1.0) #define lowbit(x) ((x)&(-x)) #define fl() printf("flag\n") #define MOD(x) ((x%mod)+mod)%mod #define endl '\n' #define pb push_back #define lson (rt<<1) #define rson (rt<<1|1) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) template<typename T>inline void read(T &x) { x=0; static int p;p=1; static char c;c=getchar(); while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();} x*=p; } //----------------------------------------------- const int maxn=1e3+9; const int mod=1e9+7; int du[maxn]; vector<int >g[maxn]; int fa[maxn]; int main() { //FAST_IO; //freopen("input.txt","r",stdin); int n; while(~sfi(n)) { for(int i=1;i<=n;i++) du[i]=0,fa[i]=-1,g[i].clear(); for(int i=1;i<=n;i++) { int c; sfi(c); while(c--) { int v; sfi(v); g[i].pb(v); du[v]++; } } queue<int>q; for(int i=1;i<=n;i++) { if(du[i]==0) q.push(i),fa[i]=i; } bool f=1; if(q.size()!=1) { puts("NO"); continue; } int num=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(fa[v]!=fa[u]&&fa[v]!=-1) { f=0; } fa[v]=u; du[v]--; if(du[v]==0) { q.push(v); num++; } } } if(num!=n-1) f=0; if(!f) puts("NO"); else { puts("YES"); for(int i=1;i<=n;i++) { if(fa[i]!=-1&&fa[i]!=i) { printf("%d %d\n",fa[i],i); } } } } return 0; }
