가장 강력한 주문

아주 먼 옛날, 수많은 "마법 문양"을 고안한 마법사가 있었다. 그의 마법 문양 중 하나가 바닥에 그려진 방에서는 누구든 주문을 외워 마법을 쓸 수 있다. 어떤 방에서 쓸 수 있는 주문의 집합은 그 방에 그려진 문양에 따라 달라진다. 주어진 각 마법 문양에 대해, 그 문양으로 쓸 수 있는 가장 강력한 주문을 구하라.

주문은 소문자로 이루어진 문자열이다. 주문들 중에서는 사전순으로 더 앞서는 것이 더 강력하다. 문자열 $w$가 문자열 $u$보다 사전순으로 앞선다는 것은, 두 문자열이 처음으로 달라지는 위치에서 $w$의 글자가 $a < b < \dots < z$ 순서상 더 작거나, 혹은 $w$가 $u$의 접두사인 경우를 말한다. 예를 들어 "abcd"는 $c < e$이므로 "abe"보다 앞서고, "abe"는 "abef"의 접두사이므로 "abef"보다 앞선다.

마법 문양은 서로 다른 번호가 매겨진 노드들과, 그것들을 잇는 화살표들로 이루어진 그림이다. 각 화살표에는 라벨이 붙어 있는데, 이는 소문자 문자열이다. 문양에는 두 개의 특별한 노드가 있으며, 각각 별 노드(star node)와 금 노드(gold node)라 부른다. 어떤 주문이 그 문양으로 쓸 수 있게 되는 것은, 별 노드에서 금 노드까지 화살표를 따라가는 어떤 경로의 라벨들을 순서대로 이어 붙인 것과 그 주문이 일치할 때, 그리고 오직 그때뿐이다.

아래 그림은 노드 4개와 화살표 7개로 이루어진 문양의 예이다.

여기서 노드 0이 별 노드이고 노드 2가 금 노드이다. 이 문양으로 쓸 수 있는 주문의 한 예는 "abracadabra"이며, 다음 경로에서 얻어진다.

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

또 다른 예는 "oilcadabraketdadabra"이며, 다음 경로에서 얻어진다.

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

"abracadabra"는 "oilcadabraketdadabra"보다 사전순으로 앞서므로 더 강력하다. 실제로 이 문양으로 쓸 수 있는 다른 어떤 주문도 "abracadabra"보다 강력하지 않으므로, 이 문양의 답은 "abracadabra"이다.

가장 강력한 주문을 정할 수 없는 경우에는 "NO"라고 답하라. 그런 경우는 두 가지이다. 하나는 별 노드에서 금 노드로 가는 경로가 전혀 없는 경우이다. 다른 하나는 쓸 수 있는 모든 주문에 대해 항상 그보다 더 강력한 주문이 존재하는 경우이다. 아래 그림이 그 예이다. "ab"는 "b"보다 강력하고, "aab"는 "ab"보다 강력하며, 이런 식으로 계속된다. 어떤 주문이든 앞에 "a"를 붙이면 사전순으로 더 앞서는(따라서 더 강력한) 주문을 얻을 수 있다.

입력은 최대 150개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

n a s g
x_1 y_1 lab_1
x_2 y_2 lab_2
...
x_a y_a lab_a

첫 줄에는 네 정수가 주어진다. $n$은 노드의 수, $a$는 화살표의 수이며, $s$와 $g$는 각각 별 노드와 금 노드이다. 이어지는 $a$개의 줄은 각각 하나의 화살표를 나타낸다. 줄 "$x_i\ y_i\ \mathrm{lab}_i$"는 노드 $x_i$에서 노드 $y_i$로 가며 라벨이 $\mathrm{lab}_i$인 화살표를 뜻한다.

값들은 다음을 만족한다. $2 \le n \le 40$, $0 \le a \le 400$, $0 \le s, g, x_i, y_i < n$, $s \ne g$이며, 각 $\mathrm{lab}_i$는 길이가 1 이상 6 이하인 소문자 문자열이다. 자기 자신으로 돌아오는 화살표($x_i = y_i$)가 있을 수 있고, 같은 순서쌍의 노드를 잇는 화살표가 여러 개 있을 수도 있음에 유의하라.

입력의 끝은 네 개의 0으로 이루어진 줄 0 0 0 0으로 표시된다.

가장 강력한 주문

문제

입력

출력