A - パズル

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

N 個の頂点と M 本の無向辺から成る単純なグラフ(連結とは限らない)があります． N 個の頂点には，頂点 1 から順に，1,2,...,N と番号が振られています．

ある相異なる 3 つの頂点 a,b,c を選んだときに，a と b を結ぶ辺， b と c を結ぶ辺，そして c と a を結ぶ辺が存在するとき， (a,b,c) は 3 つ組であると言います．

さて，3 つ組となっている頂点 (a,b,c) を選び，

  • 頂点 a の新しい番号は頂点 c の古い番号
  • 頂点 b の新しい番号は頂点 a の古い番号
  • 頂点 c の新しい番号は頂点 b の古い番号

となるように頂点に書かれている番号を書き換える「回転」と呼ばれる操作を定義します．

この回転を任意の 3 つ組に対して任意の回数行い，最終的に各頂点に書かれている番号が頂点 1 から順に y_1,y_2,...,y_N となるようにしたいです． このような遷移が可能か不可能かを判定するプログラムを作って下さい．

入力

入力は以下の形式で標準入力から与えられる．

N M
a_1 b_1
a_2 b_2
:
a_M b_M
y_1
y_2
:
y_N
  • 1 行目には，グラフの頂点の数 N (1 ≦ N ≦ 2000) と 辺の数 M (1 ≦ M ≦ 2000) がスペース区切りで書かれている．
  • 2 行目から M 行，各辺の情報を表す異なる整数 a_i と b_i (1≦a_i,b_i≦N) がスペース区切りで書かれている．これは，グラフにおいて頂点 a_i と頂点 b_i が繋がっているという情報を表す．
  • 1+M 行目から N 行，目標のグラフの各頂点に書かれている番号を表す相異なる整数 y_1,y_2,...,y_N (1≦y_i≦N) がスペース区切りで書かれている．

出力

問題文で与えられる遷移が可能であれば "YES" を，不可能であれば "NO" を出力せよ．最後に改行すること．

入力例1

3 3
1 2
2 3
3 1
2
3
1

出力例1

YES

頂点 (1,2,3) が 3 つ組なので，回転を 2 回行うことで，目標を達成できる．

入力例2

3 2
1 2
1 3
1
3
2

出力例2

NO

3 つ組が 1 つも存在しないので回転は不可能であり，目標の番号付けは達成できない．

入力例3

8 11
1 2
1 3
2 3
2 4
2 5
3 6
4 5
5 6
6 7
6 8
7 8
6
2
3
4
5
1
7
8

出力例3

NO

どう操作を行っても，頂点 6 の番号を 1 にすることは不可能であり，目標の番号付けは達成できない．

B - カッコつけ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は「カッコつけ」です。開きカッコ(と閉じカッコ)だけからなる文字列に、新しくカッコを挿入したり削除したりするのが大好きです。 また、各文字列には「カッコ悪さ」という値が定義されます。ある文字列 S を「完璧」にするために取り除くべき文字の個数の最小値が「カッコ悪さ」です。 カッコ付けの対応に矛盾がなかった場合その文字列は「完璧」であると言います。特に、0文字の文字列も「完璧」です。

例えば ()()(())という文字列は「完璧」で、「カッコ悪さ」は 0 です。 ())は最後のカッコを取り除くと「完璧」になります。よって「カッコ悪さ」は 1 です。

高橋君は文字列 S を友人からもらいました。今からこの文字列に開きカッコや閉じカッコを挿入したり、削除したりします。 高橋君はときどき、いまの文字列うちの一部分の「カッコ悪さ」が気になります。 あなたは、高橋君が「カッコ悪さ」を質問した時に、それを求めてください。

入力

入力は以下の形式で標準入力から与えられる

Q
S
x_1 y_1 z_1
x_2 y_2 z_2
:
x_Q y_Q z_Q
  • 1 行目には高橋君が行う操作(質問含む)の回数 Q (1 ≦ Q ≦ 10^5) が与えられる。
  • 2 行目には高橋君がもらった文字列 S (1 ≦ | S | ≦ 10^5) が与えられる。
  • 3 行目からの Q 行のうち i 行目には i 番目の操作の内容を表す文字 x_i と数値 y_i, z_i が空白区切りで与えられる。
  • x_iが(のとき、開きカッコを挿入する操作を表す。y_i番目に開きカッコを挿入する操作である。このときz_iは常に0である。
  • x_iが)のとき、閉じカッコを挿入する操作を表す。y_i番目に閉じカッコを挿入する操作である。このときz_iは常に0である。
  • x_iがDのとき、削除する操作を表す。y_i番目の文字列を削除する操作である。このときz_iは常に0である。
  • x_iがQのとき、質問する操作を表す。y_i番目からz_i番目の間(端を含む)の文字列の「カッコ悪さ」を質問するということである。
  • 存在しない位置の文字を削除したり、質問したり、存在しない位置に文字を挿入するような入力は無い。また、与えられる全ての位置は1-indexedである。

出力

出力は複数行からなる。 高橋君が質問するたびにその答えを1行で出力せよ。

入力例1

5
(()
D 1 0
( 3 0
Q 1 2
) 1 0
Q 2 4

出力例1

0
1

1 回目の操作が終わったあとの状態は ()

2 回目の操作が終わったあとの状態は ())

3 回目の操作で質問されている範囲の文字列は ()

4 回目の操作が終わったあとの状態は (())

5 回目の操作で質問されている範囲の文字列は ())

入力例2

11
(()()(()
( 1 0
( 1 0
D 4 0
Q 2 6
) 5 0
D 8 0
Q 1 9
( 3 0
) 8 0
D 10 0
Q 5 10

出力例2

1
1
4

1 回目の操作が終わったあとの状態は ((()()(()

2 回目の操作が終わったあとの状態は (((()()(()

3 回目の操作が終わったあとの状態は ((()()(()

4 回目の操作で質問されている範囲の文字列は (()()

5 回目の操作が終わったあとの状態は ((())()(()

6 回目の操作が終わったあとの状態は ((())()()

7 回目の操作で質問されている範囲の文字列は ((())()()

8 回目の操作が終わったあとの状態は (((())()()

9 回目の操作が終わったあとの状態は (((())())()

10 回目の操作が終わったあとの状態は (((())()))

11 回目の操作で質問されている範囲の文字列は ))()))