Hamako Online Judge

TLE
3sec

MLE
256MB

得点
100

JOI くんの家の近くには細長い屋敷がある．この屋敷は部屋が東西に N 個並んだ構造をしており，東から i 番目の部屋を部屋 i と呼ぶ．部屋 i と部屋 i + 1 (1 ≤ i ≤ N − 1) は廊下でつながっており，廊下は双方向に通行可能である．部屋と廊下を行き来するためには鍵が必要である．鍵には種類と呼ばれる番号が付けられている．同じ種類の鍵が複数あることもある．

部屋 i や部屋 i + 1 から，部屋 i と部屋 i + 1 を結ぶ廊下に入るには，種類 C_i の鍵が必要である．

部屋 i には B_i 個の鍵が落ちている．それらの鍵の種類は A_i,j (1 ≤ j ≤ B_i) である．JOI くんは，部屋に入るとその部屋に落ちている鍵を全て拾い，以後廊下に入るのに使うことができる．

鍵は何度でも使うことができる．また，同じ鍵が複数手に入ることがあるが，1 つ持っているときと比べて特別役に立つことはない．

JOI くんは，この屋敷で迷子になったときに備えて，以下の形式のクエリに答えるプログラムを書くことにした．

JOI くんが鍵を 1 つも持っていない状態で部屋 x に迷い込んだとき，部屋 y に到達することはできるか?

あなたの仕事は，JOI くんに代わってこのクエリに答えるプログラムを書くことである．

課題

屋敷の情報とクエリが与えられたとき，それぞれのクエリに対し，鍵を 1 つも持っていない状態で部屋に迷い込んだとき，部屋から部屋に到達することができるかを判定するプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

1 行目には整数 N が書かれている．これは屋敷には部屋が N 個あることを表す．
2 行目には N − 1 個の整数 C₁, C₂, ..., C_N−1 が空白を区切りとして書かれている．これらは，部屋 i や部屋 i + 1 から，部屋 i と部屋 i + 1 を結ぶ廊下に入るには種類 C_i の鍵が必要であることを表す．
続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，1 以上の整数 B_i と，B_i 個の整数 A_i,1, A_i,2, ..., A_{i,B_i} が空白を区切りとして書かれている．これは部屋 i には鍵が B_i 個落ちており，それらの鍵の種類が A_i,j (1 ≤ j ≤ B_i) であることを表す．
次の行には整数 Q が書かれている．これはクエリが Q 個与えられることを表す．
続く Q 行のうちの k 行目 (1 ≤ k ≤ Q) には，2 個の整数 X_k と Y_k が空白を区切りとして書かれている．これらは，k 番目のクエリが，鍵を 1 つも持っていない状態で部屋 X_k に迷い込んだとき，部屋 X_k から部屋 Y_k に到達できるかを尋ねるものであることを表す．

出力

標準出力に Q 行で出力せよ．Q 行のうちの k 行目 (1 ≤ k ≤ Q) には，鍵を 1 つも持っていない状態で部屋 X_k に迷い込んだとき，部屋 X_k から部屋 Y_k に到達することができるなら YES を，そうでないなら NO を出力せよ．

制限

すべての入力データは以下の条件を満たす．

2 ≤ N ≤ 500 000．
1 ≤ Q ≤ 500 000．
1 ≤ B₁ + B₂ + ··· + B_N ≤ 500 000．
1 ≤ B_i ≤ N (1 ≤ i ≤ N)．
1 ≤ C_i ≤ N (1 ≤ i ≤ N − 1)．
1 ≤ A_i,j ≤ N (1 ≤ i ≤ N, 1 ≤ j ≤ B_i)．
B_i 個の整数 A_i,1, ..., A_{i,B_i} は互いに異なる (1 ≤ i ≤ N)．
1 ≤ X_k ≤ N (1 ≤ k ≤ Q)．
1 ≤ Y_k ≤ N (1 ≤ k ≤ Q)．
X_k ≠ Y_k (1 ≤ k ≤ Q)．

小課題

この課題では小課題は全部で 4 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題 1 [5 点]

N ≤ 5 000．
Q ≤ 5 000．
B₁ + B₂ + ··· + B_N ≤ 5 000．

小課題 2 [5 点]

N ≤ 5 000．
B₁ + B₂ + ··· + B_N ≤ 5 000．

小課題 3 [15 点]

N ≤ 100 000．
C_i ≤ 20 (1 ≤ i ≤ N − 1)．
A_i,j ≤ 20 (1 ≤ i ≤ N, 1 ≤ j ≤ B_i)．

小課題 4 [75 点]

追加の制限はない．

入出力例

入力例 1

出力例 1

YES
NO
NO
YES

1 つ目のクエリでは，部屋 2, 1, 2, 3, 4 の順に移動することで，部屋 4 に到達することができる．
2 つ目のクエリでは，部屋 3, 4 にしか行くことができず，手に入れられる鍵の種類は 1, 3 のみなので，部屋 2 に到達することができない．
3 つ目のクエリでは，部屋 4 から部屋 5 に行く種類 4 の鍵を手に入れることができないため，部屋 5 に到達することができない．
4 つ目のクエリでは，部屋 5, 4, 3 の順に移動することで，部屋 3 に到達することができる．

入力例 2

出力例 2

YES
NO
YES

入力例 3

7
6 3 4 1 2 5
1 1
1 5
1 1
1 1
2 2 3
1 4
1 6
3
4 1
5 3
4 7

出力例 3

YES
NO
YES

0658 - 細長い屋敷 (Long Mansion)

課題

入力

出力

制限

小課題