AGC029F
有(n)个点。给你(n-1)个点集(E_i)，你要在每个点集中选择两个点，在它们之间连一条边，要求最后形成一棵树。
要求输出方案。
(nle 10^5)
(sum |E_i|le 2*10^5)
独自思考的时候想到了个不太好写的做法。大概描述：对每个点集新建一个点（记作方点），连向点集内的所有点（记作圆点）。在形成的图中搞出dfs树，设(f_{i,j})表示搞完了(i)的子树，(j)为(i)的子树中存在一条返祖边连向深度为(j)的祖先。至于它的值。。。大概是用来记转移的前驱的。根据圆点还是方点分类，用线段树优化转移。由于要输出方案，所以要搞个可持久化线段树合并，用些奇怪的方法来维护它的上一个状态。。。
显然不可以写。于是我看了题解。
假如有个集合(S)为所有点集的集合的子集，就是说(Sin{E_1,E_2,E_3,dots,E_{n-1}})。
设(f(S)={u|uin E_i in S})
如果(f(S)le |S|)，那么不合法。显然，有(|S|)条边但是点数小于等于(|S|)，那么是连不出一棵树的。
所以(f(S)>|S|)。
这个东西是有解的必要条件。后面用构造证明这也是充分条件。
看起来像个Hall定理，于是考虑二分图：左边一排(n)个点，右边一排(n-1)个点集。一个点集和一个点配对（相当于决定儿子是谁）。
跑个二分图匹配。
设左边唯一一个没有被匹配的点为(r)。然后从它开始dfs：找到和它相连的没有遍历过的点集，再到和这个点集相连的点。就这样dfs下去。如果遍历完了所有的点，那么就有解了。
如果没有遍历完所有的点，那么已经遍历的点中，(左边=右边+1)。所以剩下的(左边=右边)。那它就不满足前面的那个必要条件，所以没有解。
dinic跑二分图时间复杂度是(O(msqrt n))的？？长见识了。。。
LYL网络流第一次死了。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define M 200010
#define INF 1000000000
int n;
struct EDGE{
int to,c;
EDGE *las;
} e[M*2+N*4];
int ne;
EDGE *last[N*2];
void link(int u,int v,int c){
e[ne]={v,c,last[u]};
last[u]=e+ne++;
}
int S,T;
int gap[N*2],BZ,dis[N*2];
EDGE *cur[N*2];
#define rev(ei) (e+(int((ei)-e)^1))
bool getdis(){
static int q[N*2];
memcpy(cur,last,sizeof(EDGE*)*(T+1));
memset(dis,0,sizeof(int)*(T+1));
dis[S]=1;
q[1]=S;
int head=1,tail=1;
while (head<=tail){
int x=q[head++];
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->c && !dis[ei->to]){
dis[ei->to]=dis[x]+1;
q[++tail]=ei->to;
}
}
return dis[T];
}
int dfs(int x,int s){
if (x==T)
return s;
int have=0;
for (EDGE *&ei=cur[x];ei;ei=ei->las)
if (ei->c && dis[ei->to]==dis[x]+1){
int t=dfs(ei->to,min(ei->c,s-have));
ei->c-=t,rev(ei)->c+=t,have+=t;
if (have==s) return s;
}
cur[x]=last[x];
return have;
}
int flow(){
gap[0]=T;
BZ=1;
int r=0;
while (getdis()){
int tmp;
do{
tmp=dfs(S,INF);
r+=tmp;
}
while (tmp);
}
return r;
}
int bel[N];
bool vis[N*2];
int ans[N][2];
int cnt;
void dfs(int x){
vis[x]=1;
++cnt;
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->to!=S && !vis[ei->to]){
vis[ei->to]=1;
ans[ei->to-n][0]=x;
ans[ei->to-n][1]=bel[ei->to-n];
dfs(bel[ei->to-n]);
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<n;++i){
int k;
scanf("%d",&k);
for (int j=0;j<k;++j){
int x;
scanf("%d",&x);
link(x,n+i,1),link(n+i,x,0);
}
}
S=n+n-1+1,T=n+n-1+2;
for (int i=1;i<=n;++i)
link(S,i,1),link(i,S,0);
for (int i=1;i<n;++i)
link(n+i,T,1),link(T,n+i,0);
int f=flow();
if (f!=n-1){
printf("-1
");
return 0;
}
for (int i=1;i<n;++i)
for (EDGE *ei=last[n+i];ei;ei=ei->las)
if (ei->to!=T && ei->c)
bel[i]=ei->to;
int r=0;
for (int i=1;i<=n;++i)
for (EDGE *ei=last[i];ei;ei=ei->las)
if (ei->to==S && !ei->c)
r=i;
dfs(r);
if (cnt<n)
printf("-1
");
else
for (int i=1;i<n;++i)
printf("%d %d
",ans[i][0],ans[i][1]);
return 0;
}