D: みゃんぱすーれつ - Myampus Sequence -

物語

みゃんぱすー． ウチ，田舎の分校に通う小学一年生なん．

あんなー，今日の授業はプログラミングだったん． みんな苦戦してたけど，まっつんのにぃにぃ，凄い勢いでタイピングしてたん． さすが中三なんなー．

にぃにぃ，プログラムが完成してどこか行ってしまったん． そんで，画面見たら，色んな数列が出力されてたん． だんだん出力と同じような数列を書きたくなったん，ウチ，出力テキストに同じような数列をいくつも書き加えてたん． そしたら，にぃにぃが戻ってきて，すごい怒られたん． ウチ，にぃにぃの声初めて聞いたから，びっくりしたん．

でな，にぃにぃに謝ってプログラムを見せてもらったん． プログラムが出力してたん，「みゃんぱすーれつ」いうん． 数列がみゃんぱすーれつか調べて，にぃにぃの機嫌を直したいん． でも，ウチ，プログラミング初めてなん，教えてほしいのん．

問題

N 個の整数からなる数列と M 個の関数からなるプログラムが与えられる．プログラムが開始されると 1 番目の関数を呼び出し，この関数の処理が終了すると，プログラムは終了する．また， i (1 ≤ i ≤ M) 番目の関数は，次のどちらか一方の処理を行い，関数の処理を終了する．

• 整数 a_i を出力する．
• b_i (1 ≤ b_i ≤ M) 番目の関数を呼び出し，呼び出した関数の処理が終了したら， c_i (1 ≤ c_i ≤ M) 番目の関数を呼び出し，呼び出した関数の処理の終了を待つ．

どちらの処理を行うかは，処理の度にランダムに決定される．つまり，プログラムが開始されると1個の数列を出力して終了する．ここで，プログラムが出力する数列としてあり得るものを「みゃんぱすーれつ」と定義する．

与えられた数列がみゃんぱすーれつか判定せよ．

入力形式

入力は次の形式で与えられる．

N
x_1 ... x_N
M
a_1 b_1 c_1
...
a_M b_M c_M

1行目に，判定すべき数列の長さ N が与えられる． 2行目に，判定すべき整数列 x_1, x_2, ..., x_N が順に与えられる． 3行目に，関数の個数 M が与えられる． i + 3 ( 1 ≤ i ≤ M) 行目に， i 番目の関数の情報を表す a_i, b_i, c_i が順に与えられる．

入力は次の制約を満たす．

• 1 ≤ N ≤ 100
• i = 1, ..., N に対して， x_i は 0 ≤ x_i ≤ 9 を満たす整数
• 1 ≤ M ≤ 10
• i = 1, ..., M に対して， a_i は 0 ≤ a_i ≤ 9 を満たす整数
• i = 1, ..., M に対して， b_i は 1 ≤ b_i ≤ M を満たす整数
• i = 1, ..., M に対して， c_i は 1 ≤ c_i ≤ M を満たす整数

出力形式

与えれた数列がみゃんぱすーれつの場合には “Yes” と出力し，数列がみゃんぱすーれつではない場合には “No” と出力せよ．また，出力の最後に改行せよ．

入力例1

3
3 5 3
3
5 2 3
3 3 1
7 1 2

出力例1

Yes

次のようにプログラムが動作すると，与えられた数列を生成します．

1. プログラムが関数 1 を呼び出す．
2. 関数 1 が関数 2 と関数 3 を順に呼び出す．
3. 関数 2 が 3 を出力する．
4. 関数 3 が関数 1 と関数 2 を順に呼び出す．
5. 関数 1 が 5 を出力する．
6. 関数 2 が 3 を出力する．

入力例2

10
9 9 9 9 9 9 9 9 9 9
4
6 2 3
7 3 1
8 1 2
9 2 1

出力例2

No

どのような処理を行っても，関数 4 を呼び出すことがないので， 9 を出力することができません．そのため， 9 を含む数列を出力することはできません．

入力例3

2
2 4
4
1 2 3
2 1 1
3 4 1
4 1 1

出力例3

No

このプログラムは， 2, 4, 1 のように， 2, 4 を含む数列を生成することがありますが， 2, 4 自体を生成することはありません．

Note

Link

 

---