問題文

「人には定めの星がある 綺羅星 明星 流れ星」

ここは惑星オリヴェル,時刻は地球と同じ21時. 空にはNN個の星が所狭しと輝いており,右からii番目の星の色はcic_iで,輝度はbib_iです. ci=c_i=Rのときii番目の星は赤色, ci=c_i=Gのときii番目の星は緑色, ci=c_i=Bのときii番目の星は青色に輝いており,星は必ずこの33色のうちいずれか11色で輝いています. また,この世に同じ顔の人がいないように,星も同じ輝度であるものはありません.

惑星オリヴェルで星を見ているあなたに星に関する情報がMM個与えられます. ii個目の情報は星xix_iと星yiy_i11本の線で結ばれているというものです.

ここで,線で結ばれた星どうしの集合を星座と呼びます.

また,惑星オリヴェルでは,以下の条件を満たす星のことをRedSpicaと呼びます.

  • その星座の中で11番輝度が高く,色が赤である

今見えるNN個の星のうち,RedSpicaが何個見えるかを数えてください.

制約

  • 1N1051 \leq N \leq 10^5
  • 1bi1091 \leq b_i \leq 10^9
  • ci{c_i \in \{R,,G,,B}\}
  • iji \neq jならばbibjb_i \neq b_j
  • 0Mmin(105,n(n1)2)0 \leq M \leq \min(10^5, \frac{n(n-1)}{2} )
  • 1xi,yiN1 \leq x_i , y_i \leq N
  • xiyix_i \neq y_i
  • 入力される値はすべて整数である

入力

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

NN
b1b_1b2b_2 \cdots bNb_N
c1c_1c2c_2 \cdots cNc_N
MM
x1x_1y1y_1
x2x_2y2y_2
\vdots
xMx_MyMy_M

出力

惑星オリヴェルから見えるRedSpicaの数を出力せよ.

サンプル

入力1
6
3 1 4 5 9 2
R G B G R R
3
1 2
2 3
4 5
出力1
2

惑星オリヴェルでは今33つの星座を見ることができます.

  • 11と星22と星33からなる星座のうち11番輝度が高い星は星33であり,色は青であるためこの星はRedSpicaではありません
  • 44と星55からなる星座のうち11番輝度が高い星は星55であり,色は赤であるためこの星はRedSpicaです
  • 66からなる星座のうち11番輝度が高い星は星66であり,色は赤であるためこの星はRedSpicaです

よって今見えている66つの星のうちRedSpicaは22個です.

入力2
9
412 404 389 359 344 339 338 279 97
R B G R G R B G R
8
1 9
3 9
2 4
4 5
9 5
5 7
6 7
8 6
出力2
1

頂に立つのはただ1人

提出


Go (1.21)