题目描述

给出 $n$ 个点 $m$ 条边的无向图，给每条边定向得到有向无环图，使得最长路最短。

输入格式

第一行一个数 $m$。

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

输出格式

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

3
P Q
Q R
R P

1

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 15$，$1\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}\}$，$u_i\not =v_i$。