#P4160. [Neerc2009]Exclusive Access 2

    ID: 3375 传统题 2000ms 128MiB 尝试: 185 已通过: 63 难度: 7 上传者: 标签>CF2200提高顶点着色独立集子集 DP子掩码递推 (s-1)&masklowbit对称性去重杂项

[Neerc2009]Exclusive Access 2

题目描述

给出 nn 个点 mm 条边的无向图,给每条边定向得到有向无环图,使得最长路最短。

输入格式

第一行一个数 mm。

接下来 mm 行,每行两个大写字母 ui,viu_i,v_i 表示一条 ui,viu_i,v_i 之间的边,细节参见数据规模与约定一栏。

输出格式

第一行输出最短可能的最长路长度减一后的值。

3
P Q
Q R
R P
1

数据规模与约定

对于 100%100\% 的数据,1≤n≤151\leq n\leq 15,1≤m≤1001\leq m\leq 100,$u_i,v_i\in\{\texttt{L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}\}$,ui≠viu_i\not =v_i。