怎么唯一一篇题解这么抽象，完全看不懂
。
给定一张无向图，求给这张图定向成 DAG 之后的最长路最短是多少。转化一下变成对 DAG 进行分层，每一层之间的点没有连边，使得层数尽可能少，那么最后的层数就是答案。
那么就求出若干个独立集，让独立集总数尽可能少。这是经典的色数问题，我们使用状压 DP，可以在 \(\mathcal O(3^n)\) 的复杂度下解决。
具体方法是设 \(f_S\) 表示当前选择的点的集合为 \(S\) 最少需要分成几个独立集。转移式子是平凡的，即 \(f_{S} = \min_{T \subseteq S \wedge T \text{是独立集}}~~~~ \{ f_{S \oplus T} \} + 1\)。还需要做的就是预处理出哪些集合状态是独立集，暴力枚举集合，枚举集合中的两两点判断即可，这部分复杂度是 \(\mathcal O(2^n \times n^2)\)。
至于具体的定向方案，我们只需要给几个独立集每个分配一个层数，然后让层数小的统一指向层数大的即可，于是我们需要知道钦定出来的每个独立集具体包含哪些元素，记一个前驱数组看是由什么状态转移而来即可。
代码实现用了记搜，总复杂度是 \(\mathcal O(n + 2^n \times n^2 + 3^n)\)。
#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
template<typename T=long long> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
putchar(ch);
return;
}
namespace MyTool
{
static const int Mod=998244353;
template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
inline void Madd(int &a,int b) {a=a+b>Mod?a+b-Mod:a+b;}
inline void Mdel(int &a,int b) {a=a-b<0?a-b+Mod:a-b;}
inline void Mmul(int &a,int b) {a=1ll*a*b%Mod;}
inline void Mmod(int &a) {a=(a%Mod+Mod)%Mod;}
inline int Cadd(int a,int b) {return a+b>=Mod?a+b-Mod:a+b;}
inline int Cdel(int a,int b) {return a-b<0?a-b+Mod:a-b;}
inline int Cmul(int a,int b) {return a*b%Mod;}
inline int Cmod(int a) {return (a%Mod+Mod)%Mod;}
inline int gcd(int a,int b) {return b?gcd(b,a%b):a;}
inline int qpow(int a,int b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
inline int qmul(int a,int b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
template<typename T> inline T power(T x) {return x*x;}
}
using namespace MyTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=16;
static const int inf=2147483647;
static const int INF=4557430888798830399;
static const int mod=1e9+7;
static const int bas=131;
static const int N=15;
int n,G[MAX][MAX],d[MAX],k;
struct edge{char x,y;}e[MAX<<3];
int all,f[1<<MAX],g[1<<MAX],pre[1<<MAX];
void dfs(int S)
{
if(!S) return f[S]=0,void();
if(~f[S]) return;
f[S]=INF;
for(int T=S;T;T=S&(T-1)) if(!g[T])
{
dfs(S^T);
if(f[S^T]+1<f[S]) f[S]=f[S^T]+1,pre[S]=S^T;
}
return;
}
inline void lmy_forever()
{
while(scanf("%lld",&n)!=EOF)
{
all=0,k=0;
memset(G,0,sizeof G),memset(f,-1,sizeof f);
memset(d,0,sizeof d),memset(g,0,sizeof g);
for(int i=1;i<=n;++i)
{
scanf(" %c %c",&e[i].x,&e[i].y);
all|=1<<(e[i].x-'L'),all|=1<<(e[i].y-'L');
G[e[i].x-'L'][e[i].y-'L']=G[e[i].y-'L'][e[i].x-'L']=1;
}
for(int S=all;S;S=all&(S-1))
for(int i=0;i<N;++i) if(S>>i&1)
for(int j=0;j<N;++j) if(S>>j&1)
if(i!=j&&G[i][j])
g[S]=1;
dfs(all),write(f[all]-2,'\n');
while(all)
{
for(int i=0;i<N;++i) if(all>>i&1) d[i]=k;
all=pre[all],++k;
}
for(int i=1;i<=n;++i)
{
if(d[e[i].x-'L']>d[e[i].y-'L']) Swp(e[i].x,e[i].y);
putchar(e[i].x),putchar(' '),putchar(e[i].y),putchar('\n');
}
}
return;
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
LgxTpre::lmy_forever();
cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}