The Most Powerful Spell

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem E: 最強の呪文

昔々,多くの「魔法の紋様」を発明した魔法使いがいた. 彼の発明した魔法の紋様が床に描かれた部屋では, 呪文を唱えることで,誰でも魔法が使えるようになるのだ! ただし,使える呪文は紋様によってまちまちである. あなたの仕事は,指定された魔法の紋様に対し, それによって使用可能となる呪文のうち,最強のものを突き止めることだ.

呪文は,英小文字の文字列であり, 特に辞書順で早ければ早い呪文であるほど,強い呪文である. ここで文字列 w が文字列 u より辞書順で早いとは, w と u とで異なる最初の文字が a<b<...<z の順序で小さいか, または w が u の接頭辞であることを言う. 例として,"abcd" は "abe" より早く(文字 c は e より小さいため), また,"abe" は "abef" より早い(接頭辞になっているため).

魔法の紋様は,番号のついた 節点 と,それらを結ぶ矢印 からなる図形である. 矢印には ラベル と呼ばれる小文字の文字列がついている. また,スターゴールド と呼ばれる, 二つの特別な節点がある. 魔法の紋様によって使えるようになる呪文とはすなわち, その紋様のスターからゴールドへと矢印をたどって得られるラベルを順に結合して得られる文字列である.

次に,四つの節点と7本の矢印からなる例を図示する.

picture: sample dataset 1

0 がスター,2 がゴールドである. この魔法の紋様によって,例えば

     0 --"abra"--> 1 --"cada"--> 3 --"bra"--> 2

という経路から得られる呪文 "abracadabra" が使えるようになる.他には,

     0 --"oil"--> 1 --"cada"--> 3 --"bra"--> 2 --"ket"--> 3 --"da"--> 3 --"da"--> 3 --"bra"--> 2

から得られる "oilcadabraketdadabra" などもある. "abracadabra" と "oilcadabraketdadabra" では前者の方が辞書順で早いので,より強い呪文である. 実は,この魔法の紋様で使用可能となる呪文で "abracadabra" 以上に強いものは存在しない. 従ってこの場合,あなたが求めるべき答えは "abracadabra" となる.

もしも,最強の呪文が定められないときには,"NO" と答えて欲しい. これには二つの場合がある.一つは,スターからゴールドへ到達できない場合である. もう一つは,どんな呪文をとっても, それよりさらに強い呪文が存在するような場合である. たとえば次の図のような魔法の紋様では, "b" よりも "ab" が強く, "ab" よりも "aab" が強いといったように, どの呪文をとってもさらに一つ a を増やすと,辞書順で早い,より強い呪文となる.

picture: sample dataset 2

Input

入力は最大で150個のデータセットからなる. 各データセットの形式は次のとおりである.

n a s g
x1 y1 lab1
x2 y2 lab2
...
xa ya laba

データセットの最初の行は4個の整数を含む.n は節点の数,a は矢印の数を表す. sg はそれぞれスターとゴールドの番号を示す. 続く a 行はそれぞれ2個の整数と1個の文字列からなり,矢印の情報を表す. xi yi labi という行は, 節点 xi から出て節点 yi を指す, ラベルが labi の矢印を表している. データセット中の値は次の条件を満たす: 2 ≤ n ≤ 40, 0 ≤ a ≤ 400, 0 ≤ s, g, xi , yi < n. sg, labi は長さ1以上6以下の,英小文字のみからなる文字列である. 矢印の両端が同一節点の場合 (xi = yi ) や, 節点の対を複数の矢印が結ぶ場合 (異なる i, j に対し xi = xj かつ yi = yj ) もあり得ることに注意して欲しい.

入力の終わりは4個のゼロからなる行によって与えられる.

Output

各データセットについて,最も強い呪文が存在すれば,それぞれ1行に出力しなさい. 存在しない場合は NO を1行に出力しなさい. 各出力行はこれ以外の文字を含んではならない.

Sample Input

4 7 0 2
0 1 abra
0 1 oil
2 0 ket
1 3 cada
3 3 da
3 2 bra
2 3 ket
2 2 0 1
0 0 a
0 1 b
5 6 3 0
3 1 op
3 2 op
3 4 opq
1 0 st
2 0 qr
4 0 r
2 1 0 1
1 1 loooop
0 0 0 0

Output for the Sample Input

abracadabra
NO
opqr
NO

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2010-07-02
http://icpc2010.honiden.nii.ac.jp/