Lexicographically Greatest Walk

(writerが過去にXで公開した問題です。)

問題文

$N$ 頂点 $M$ 辺の有向グラフ $G$ が与えられます。$G$ の各頂点は $1$ から $N$ の、各辺は $1$ から $M$ の整数で番号づけられており、 $1\le i\le M$ について、辺 $i$ は頂点 $U_i$ から頂点 $V_i$ に向かう辺です。また、 $1\le i\le N$ について、頂点 $i$ には英小文字 $C_i$ が書かれています。

空でない、有限の長さの英小文字列 $X$ が次の条件を満たす時、$X$ を「生成可能文字列」と呼びます。

• $G$ 上のあるウォーク $P=(P_1,P_2,\cdots,P_{|P|})$ が存在して、その長さ $|P|$ は $X$ の長さに等しく、かつ各 $1\le i\le |P|$ について $C_{P_i}$ は $X$ の $i$ 文字目に等しい。

生成可能文字列全体の集合を $S$ とします。 $S$ に辞書順における最大元が存在するか判定し、存在するならばそれを出力して下さい。

制約

• $1\le N,M\le 5000$
• $1\le U_i,V_i \le N(1\le i\le M)$
• $(U_i,V_i)\ne (U_j,V_j)(1\le i < j\le M)$
• $C_i$ は英小文字 $(1\le i\le N)$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

$S$ に辞書順における最大元が存在しない場合、$1$ 行目に No と出力せよ。存在する場合、 $1$ 行目に Yes と出力し、 $2$ 行目にその最大元を出力せよ。

サンプル 1

入力

3 3
1 2
2 2
1 3
b a b

出力

Yes
bb

生成可能文字列の例として b,aa,ba,baaaa,bb などが存在します。bb は bb を除く任意の生成可能文字列よりも辞書順で大きいことが証明できるので、答えは bb になります。

サンプル 2

入力

1 1
1 1
a

出力

No

生成可能文字列の例として、a,aa,aaa などが存在します。任意の生成可能文字列について、それよりも辞書順で大きな生成可能文字列が存在することが証明できるので、辞書順最大の生成可能文字列は存在しません。