题意大概就是给你 \(n-1\) 个点集，全集是 \(\{1,2,\dots, n\}\)，现在要从每个点点集中抽出两个点来连边，最终形成一棵树。让你输出方案或判断无解。\(n\) 有 \(10^5\)，所有集合大小之和不超过 \(2\times 10^5\)。
考虑构造，儿子向父亲连边。也就是说，每个集合最后都是儿子 \(\to\) 父亲的一条边，那么我们可以随便选一个点作为跟，其余点肯定对应一个集合，表示这个集合所对应的边，一端是他，另一端是他父亲。其实也就是一个匹配，左边是除了根节点以外的所有点，右边是所有点集。点与点集有边当且仅当这个点在点集中出现。
显然地，如果这个匹配无解那么最终肯定无解，因为根本找不到一个完美的儿子 \(\to\) 父亲的映射。找到匹配之后我们把根加上去，跟前面的连法一样。如果连上之后这张图仍然不连通，那么显然无解，因为两个独立的连通块显然没有生成树。
那如果上面的判掉之后是否就一定有解了呢？我们考虑构造解。我们从根节点开始 bfs，我们考虑根节点所有连出去的集合，这些集合的匹配点的父亲都定作是这个根，然后这样递归下去。不难发现，这样做是肯定有解的。
考虑复杂度，边数 \(m\) 是集合的总大小，用 Dinic 做二分图匹配，复杂度 \(\mathcal{O}(m\sqrt{n})\)，之后的构造解复杂度 \(\mathcal{O}(m)\)，所以总复杂度 \(\mathcal{O}(m\sqrt{n})\)。
cpp
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
inline char gc() {
static const int L = 233333;
static char sxd[L], *sss = sxd, *ttt = sxd;
if (sss == ttt) {
ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
if (sss == ttt) {
return EOF;
}
}
return *sss++;
}
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
char dd;
for (; !isalpha(c); dd);
return c;
}
inline char readchar() {
char dd;
for (; c == ' '; dd);
return c;
}
template <class T>
inline bool read(T& x) {
bool flg = false;
char dd;
x = 0;
for (; !isdigit(c); dd) {
if (c == '-') {
flg = true;
} else if(c == EOF) {
return false;
}
}
for (; isdigit(c); dd) {
x = (x * 10) + (c ^ 48);
}
if (flg) {
x = -x;
}
return true;
}
#undef dd
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x | 48);
return;
}
write(x / 10);
putchar((x % 10) | 48);
}
template <class T>
inline void writesp(T x) {
write(x);
putchar(' ');
}
template <class T>
inline void writeln(T x) {
write(x);
puts("");
}
#define lowbit(x) (x & -x)
namespace dfcmd {
const int maxn = 200005;
const int inf = 0x3f3f3f3f;
struct Edge {
int to, nxt, flow;
} e[maxn * 10];
int first[maxn];
int first_bak[maxn];
inline void add_edge(int from, int to) {
static int cnt = -1;
e[++cnt].nxt = first[from];
first[from] = cnt;
e[cnt].to = to;
e[cnt].flow = 1;
e[++cnt].nxt = first[to];
first[to] = cnt;
e[cnt].to = from;
e[cnt].flow = 0;
}
int n, nn, S, T;
vector<int> dian[maxn];
vector<int> too[maxn];
int dep[maxn];
inline bool bfs() {
for (int i = 1; i <= n << 1; ++i) {
first[i] = first_bak[i];
}
queue<int> q;
memset(dep, 0, sizeof(dep));
dep[S] = 1;
q.push(S);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = first[now]; ~i; i = e[i].nxt) {
int to = e[i].to;
if (!dep[to] && e[i].flow) {
dep[to] = dep[now] + 1;
q.push(to);
}
}
}
return dep[T];
}
inline int dfs(int now, int all) {
if (now == T) {
return all;
}
int flow = 0;
for (int i = first[now]; ~i; i = e[i].nxt) {
first[now] = i;
int to = e[i].to, f;
if (e[i].flow && dep[to] == dep[now] + 1 && (f = dfs(to, min(e[i].flow, all)))) {
all -= f;
flow += f;
e[i].flow -= f;
e[i ^ 1].flow += f;
}
}
return flow;
}
inline int Dinic() {
int ans = 0;
while (bfs()) {
ans += dfs(S, inf);
}
return ans;
}
int pp[maxn];
bool viss[maxn];
pair<int, int> ee[maxn];
inline int getans() {
for (int now = 1; now < n; ++now) {
for (int i = first[now]; ~i; i = e[i].nxt) {
int to = e[i].to;
if (!e[i].flow) {
pp[now] = to;
pp[to] = now;
break;
}
}
}
queue<int> q;
while (!q.empty()) {
q.pop();
}
q.push(n);
memset(viss, 0, sizeof(viss));
viss[n] = true;
int ans = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto jh : too[now]) {
if (!viss[pp[jh]]) {
viss[pp[jh]] = true;
ee[jh] = make_pair(now, pp[jh]);
ans++;
q.push(pp[jh]);
}
}
}
return ans;
}
int Main() {
read(n);
memset(first, 0xff, sizeof(first));
for (int i = 1, cnt, xx; i < n; ++i) {
read(cnt);
while (cnt--) {
read(xx);
dian[i + n - 1].push_back(xx);
too[xx].push_back(i + n - 1);
if (xx != n) {
add_edge(xx, i + n - 1);
}
}
}
nn = (n - 1) << 1;
S = ++nn, T = ++nn;
for (int i = 1; i < n; ++i) {
add_edge(S, i);
}
for (int i = 1; i < n; ++i) {
add_edge(i + n - 1, T);
}
for (int i = 1; i <= n << 1; ++i) {
first_bak[i] = first[i];
}
int ff = Dinic();
if (ff != n - 1) {
puts("-1");
return 0;
}
if (getans() != n - 1) {
puts("-1");
return 0;
}
for (int i = 1; i < n; ++i) {
writesp(ee[i + n - 1].first), writeln(ee[i + n - 1].second);
}
return 0;
}
}
int main() {
return dfcmd::Main();
}