17699번 - Long Mansion 서브태스크다국어

There is a wide mansion near JOI-kun’s house. The mansion has N rooms located in a row from east to west. The i-th room from the eastmost room is called the room i. For each i with 1 ≤ i ≤ N −1, the room i and the room i + 1 are connected by a corridor. We can pass corridors in both directions. We need a key to enter a corridor from a room. Each key has a number called the type. More than one keys can have the same type.

From the room i or the room i + 1, we need a key of type C_i to enter a corridor between them.

There are B_i keys in the room i. Their types are A_{i, j} (1 ≤ j ≤ B_i). If JOI-kun enters a room, he will pick up all the keys in that room. After that, he can use them to enter corridors.

JOI-kun can use keys as many times as he wants. Sometimes, he gets several keys of the same type. But, he has no special advantage to have several keys of the same type compared with the case where he has only one key of that type.

To deal with the situation where he gets lost in the mansion, JOI-kun plans to write a program which answers the following queries:

• If JOI-kun comes into the room x without any keys, can he move to the room y?

Your task is to write a program which answers the above queries, instead of JOI-kun.

Given information of the mansion and the queries, write a program which determines, for each query, whether he can move from a room to another room assuming he is now in the mansion without any keys.

Read the following data from the standard input.

• The first line of input contains an integer N, the number of rooms in the mansion.
• The second line of input contains N − 1 space separated integers C₁, C₂, . . . ,C_N−1. This means we need a key of type C_i to enter a corridor connecting the room i and the room i + 1.
• The i-th line (1 ≤ i ≤ N) of the following N lines contains a positive integer B_i, and B_i space separated integers A_i,1, A_i,2, . . . , A_i,Bi. This means there are B_i keys in the room i, and their types are A_i,j (1 ≤ j ≤ B_i).
• The following line contains an integer Q, the number of queries.
• The k-th line (1 ≤ k ≤ Q) of the following Q lines contains two space separated integers X_k, Y_k. This means the k-th query asks whether JOI-kun can move from the room X_k to the room Y_k assuming he is now in the room X_k without any keys.

Write Q lines to the standard output. The k-th line (1 ≤ k ≤ Q) of the Q lines contains YES if he can move from the room Xk to the room Yk assuming he is now in the room Xk without any keys. Otherwise, it contains 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).
• The B_i integers A_i,1, . . . , A_i,Bi are different from each other (1 ≤ i ≤ N).
• 1 ≤ X_k ≤ N (1 ≤ k ≤ Q).
• 1 ≤ Y_k ≤ N (1 ≤ k ≤ Q).
• X_k ≠ Y_k (1 ≤ k ≤ Q).

• N ≤ 5 000.
• Q ≤ 5 000.
• B₁ + B₂ + · · · + B_N ≤ 5 000.

• N ≤ 5 000.
• B₁ + B₂ + · · · + B_N ≤ 5 000.

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

There are no additional constraints.