今天运气爆棚啊，写完调了下过了样例就直接一发入魂了，导致我立的flag倒了
由于这里给出的数只有位数的区别，因此我们很容易想到把不同位数的分开来做
我们给每个位数的数中选一个定为关键点，显然最后存在至少一种方案满足所有的边都经过至少一个关键点
那么我们考虑先把所有关键点连起来，由于当(nle 2 imes 10^5)时不同的位数只有(6)位，因此直接爆搜一下树的形态即可
接下来就考虑对于每条边((x,y))是从(x)的关键点连向(y)还是从(y)的关键点连向(x)了，我们可以把这看做一个网络流模型：
- 把(frac{m(m+1)}{2})种((x,y))边的关系看做左边的点，源点向每个点连未确定的边数（总边数减去关键点之间边数）为容量的边
- 把(m)种点看做右边的点，每个点向汇点连该位数的非关键点的点数为容量的边
- 左边的点((x,y))向右边的(x,y)连与源点到((x,y))的容量相同的边
由于这里的数据范围极小，因此保证正确性即可，复杂度什么的都是随便跑
PS：好像有Hall定理的做法比这个简洁的多，然后好像还有并查集的神仙做法，这个就跟个暴力一样的说
#include<cstdio>
#include<cstring>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=10;
int n,m,x,y,id[N][N],L[N],R[N],p[N],ans,fa[N],c[N][N],r[N][N]; char s[N];
namespace NF //Network Flow
{
const int N=100,M=10000,INF=1e9;
struct edge
{
int to,nxt,v;
}e[M]; int cnt=1,head[N],cur[N],q[N],dep[N],s,t;
inline void addedge(CI x,CI y,CI z)
{
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
}
#define to e[i].to
inline bool BFS(void)
{
RI H=0,T=1; memset(dep,0,t+1<<2); q[dep[s]=1]=s;
while (H<T)
{
int now=q[++H]; for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q[++T]=to;
}
return dep[t];
}
inline int DFS(CI now,CI tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
}
if (!ret) dep[now]=0; return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,t+1<<2),ret+=DFS(s,t,INF); return ret;
}
inline void clear(void)
{
cnt=1; for (RI i=s;i<=t;++i) head[i]=0;
}
};
inline void check(void)
{
RI i,j,k,t; for (i=1;i<=m;++i) for (j=i;j<=m;++j) r[i][j]=c[i][j];
for (i=2;i<=m;++i)
{
bool flag=0; int c=0; for (j=i;c<=m&&!flag;++c,j=fa[j])
if (j==1) flag=1; if (!flag) return; int x=i,y=fa[i];
if (x>y) swap(x,y); if (r[x][y]) --r[x][y]; else return;
}
for (NF::clear(),NF::s=0,NF::t=m*(m+1)/2+m+1,i=1;i<=m;++i) for (j=i;j<=m;++j)
{
NF::addedge(NF::s,id[i][j],r[i][j]);
NF::addedge(id[i][j],m*(m+1)/2+i,r[i][j]);
if (i!=j) NF::addedge(id[i][j],m*(m+1)/2+j,r[i][j]);
}
int sum=0; for (i=1;i<=m;++i) NF::addedge(m*(m+1)/2+i,NF::t,R[i]-L[i]),sum+=R[i]-L[i];
if (NF::Dinic()!=sum) return;
for (i=2;i<=m;++i) printf("%d %d
",L[i],L[fa[i]]); for (i=1;i<=m;++i) p[i]=L[i];
for (i=1;i<=m;++i) for (j=i;j<=m;++j) for (k=NF::head[id[i][j]];k;k=NF::e[k].nxt)
if (NF::e[k].to!=NF::s) for (t=1;t<=r[i][j]-NF::e[k].v;++t)
printf("%d %d
",++p[NF::e[k].to-m*(m+1)/2],L[i+j-(NF::e[k].to-m*(m+1)/2)]); exit(0);
}
inline void DFS(CI now=2)
{
if (now>m) return check(); for (RI i=1;i<=m;++i)
if (i!=now) fa[now]=i,DFS(now+1);
}
int main()
{
RI i,j; for (scanf("%d",&n),x=1;x<=n;x*=10) ++m,L[m]=x,R[m]=min(x*10-1,n);
for (x=0,i=1;i<=m;++i) for (j=i;j<=m;++j) id[i][j]=++x;
for (i=1;i<n;++i)
{
scanf("%s",s+1); x=strlen(s+1); scanf("%s",s+1); y=strlen(s+1);
if (x>y) swap(x,y); ++c[x][y];
}
return DFS(),puts("-1"),0;
}