Solution
提供一种新思路。
首先考虑如何判断一个状态是否合法。
考虑把所有十进制长度一样的数缩成一个点。
这样的点的个数 (le 5)。
蒟蒻猜了一个结论：只要满足对于所有缩出来的点的子集的点的个数 > 子集内边的个数，那么就是有解的。
这时 ( t color{black}{S}color{red}{egmentTree}) 会下凡告诉你：这是对的！卡不掉！
但是这样只能判断可不可行啊，不能输出方案啊。。。
发现这个东西判断的时间复杂度很小，可以多次判断。
那么我们可以对于每一条边尝试一下可不可以删，然后连边（在原图上，让最后每一个长度只剩下一个点，剩下的特殊处理）。
Code
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define db double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int N = 100;
const int M = 2e6 + 7;
const int inf = 1e9;
int n, m, mx, p[N], minn[N], D[M][2], sum = 0;
int a[N][N];
bool check() {
L(t, 0, (1 << mx) - 1) {
int ds = 0, bs = 0;
L(i, 1, mx) if(t & (1 << (i - 1))) ds += p[i];
if(!ds) continue;
L(i, 1, mx) if(t & (1 << (i - 1))) L(j, 1, mx) if(t & (1 << (j - 1))) bs += a[i][j];
if(bs >= ds) return 0;
}
return 1;
}
int Cnt(int x) { return x == 0 ? 0 : Cnt(x / 10) + 1; }
char sa[N], sb[N];
bool get() {
L(x, 1, mx) L(i, 1, mx) if(a[x][i]) {
if(p[x] > 1) {
a[x][i] --, p[x] --;
if(check()) return printf("%d %d
", minn[x] + p[x], minn[i]), 1;
a[x][i] ++, p[x] ++;
}
if(p[i] > 1) {
a[x][i] --, p[i] --;
if(check()) return printf("%d %d
", minn[x], minn[i] + p[i]), 1;
a[x][i] ++, p[i] ++;
}
}
return 0;
}
int main() {
scanf("%d", &n), mx = Cnt(n);
L(i, 1, n) p[Cnt(i)]++;
minn[1] = 1;
L(i, 2, mx) minn[i] = minn[i - 1] * 10;
L(i, 1, n - 1) scanf("%s%s", sa, sb), D[i][0] = strlen(sa), D[i][1] = strlen(sb), a[D[i][0]][D[i][1]] ++;
if(!check()) return puts("-1"), 0;
while(get()) sum ++;
L(x, 1, mx) L(i, 1, mx) if(a[x][i]) printf("%d %d
", minn[x] + p[x] - 1, minn[i] + p[i] - 1), sum ++ ;
if(sum != n - 1) assert(0);
return 0;
}
祝大家学习愉快！
不过怎么证明那个结论是对的啊，蒟蒻思考了好久还是不懂，求解 /kel