Stamp Rally

時間制限 : 8 sec, メモリ制限 : 262144 KB

Stamp Rally

スタンプラリー

日本アミューズメントグループ (Japan Amusement Group, JAG) では,島国を模したテーマパークでのイベントを企画している. このイベントでは,参加者は橋を渡るたびに橋ごとに決められたスタンプをスタンプ帳に順番に押していく. 用意されたスタンプは以下の7種類のどれかである.

a ( ) [ ] + *

スタートからゴールまで橋を渡り歩いて,押されたスタンプの列が正しい数式になればクリアである. ただし橋を渡る向きは決まっていて,逆向きに渡ることはできない. 同じ橋を何度も渡ってよく,最終的にゴール地点に到着するのであれば一度ゴール地点に着いた後に引き続きスタンプを集めてもよい. 正しい数式とは以下の BNF で定義される <expression> である.

<expression> ::= <term> | <expression> "+" <term>
<term>       ::= <factor> | <term> "*" <factor>
<factor>     ::= "a" | "(" <expression> ")" | "[" <expression> "]"

スタート・ゴールと橋ごとのスタンプを決めたので,関係者で試しにやってみたがなかなかクリアする人が現れない. もしかしたら,この設定ではクリアすることができないのかもしれない.

スタート・ゴールと橋の情報が与えられるので,クリア可能かどうかを判定するプログラムを書きなさい.

Input

入力は50個以下のデータセットからなる.各データセットは以下の形式で表される.

n m s t
a1 b1 c1
...
am bm cm

データセットの最初の行は,空白文字1個で区切られた4個の整数 n, m, s, t からなる. n は島の数であり, 1 ≤ n ≤ 200 と仮定してよい. それぞれの島には 1 から n までの番号が付けられている. m は橋の数であり, 1 ≤ m ≤ 100,000 と仮定してよい. s はスタートの島の番号, t はゴールの島の番号である.スタートとゴールが同じ島であることもある. 続く m 行のそれぞれは,空白文字1個で区切られた2個の整数と1個の文字からなる. aibii 番目の橋によって島 ai から島 bi へ渡れることを表し, cii 番目の橋で押すスタンプを表す.ある2つの島の間に複数の橋がかかっていたり,1つの島の中で橋がかかっていたりすることもある.

入力の終わりは,4つのゼロからなる1行で示される.

Output

各データセットに対して,クリアできるならば"Yes"を,できないならば"No"を1行に出力せよ.

Sample Input

4 5 1 4
1 2 (
1 3 a
2 4 a
3 4 )
3 2 +
4 4 1 2
1 3 (
3 4 a
4 1 +
3 2 a
3 4 1 1
1 2 a
2 2 +
2 3 a
3 1 a
5 8 1 5
1 1 [
1 2 (
2 1 *
2 2 a
2 3 a
3 3 )
3 4 ]
4 5 )
2 14 1 1
1 2 a
1 2 (
1 2 )
1 2 [
1 2 ]
1 2 +
1 2 *
2 1 a
2 1 (
2 1 )
2 1 [
2 1 ]
2 1 +
2 1 *
0 0 0 0

Output for Sample Input

Yes
No
No
Yes
No

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2015, 2015-06-14
http://acm-icpc.aitea.net/