Myampus Sequence

Time Limit : 2 sec, Memory Limit : 262144 KB

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_i0 ≤ x_i ≤ 9 を満たす整数
  • 1 ≤ M ≤ 10
  • i = 1, ..., M に対して, a_i0 ≤ a_i ≤ 9 を満たす整数
  • i = 1, ..., M に対して, b_i1 ≤ b_i ≤ M を満たす整数
  • i = 1, ..., M に対して, c_i1 ≤ 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. 関数 23 を出力する.
  4. 関数 3 が関数 1 と関数 2 を順に呼び出す.
  5. 関数 15 を出力する.
  6. 関数 23 を出力する.

入力例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 自体を生成することはありません.


Source: Aizu Competitive Programming Camp 2015 Day3 , Japan, 2015-09-23