문제
준혁이의 집 근처에는 긴 멘션이 있다.
멘션은 동에서 서로 나열된 N개의 방이 있다.
동쪽으로부터 i번째 방은 i번 방이라고 부른다.
각 i에 대하여, 방 i와 방 i+1은 문을 통해 연결되어 있다.
문은 양방향으로 통행할 수 있다.
문을 통과하기 위해선 특정 종류의 열쇠가 필요하다.
여러개의 열쇠가 동일한 종류일 수 있다.
i번 방과 i+1번 방을 잇는 문을 통과하기 위해선, Ci 종류의 열쇠가 필요하다.
i번 방에는 Bi개의 열쇠가 있다. 이 열쇠들의 종류는 각 Ai,j이다.
준혁이가 방에 들어가면, 그 방에 있는 모든 열쇠를 집어간다.
이후, 준혁이는 그 열쇠들을 문을 열기 위해 사용할 수 있다.
준혁이는 열쇠를 자신이 원하는 만큼 여러번 사용할 수 있다.
즉, 같은 종류의 열쇠를 여러 개 가지고 있어도 한 개 가지고 있는 것과 동일하다.
준혁이는 멘션에서 길을 잃었을 경우에 대비해서, 다음의 프로그램을 작성하고자 한다:
- 준혁이가 방 x에 아무 열쇠도 없이 들어갔을 때, 방 y까지 이동할 수 있는가?
준혁이는 이 문제를 풀지 못했다.
여러분이 대신 풀어주자.
입력
1번 줄 : N
2번 줄 : C1, C2, ..., CN-1
3번 ~ 2+i 번 줄 : Bi, Ai,1, Ai,2, ..., Ai,Bi
N+3번 줄 : Q
N+4 ~ N+2+k번 줄 : Xk, Yk
2 <= N, Q <= 500,000
1 <= B1 + B2 + ... + BN <= 500,000
1 <= Bi, Ci, Ai,j <= N
1 <= Xk, Yk <= N
Xk != Yk
출력
Q개의 줄에 걸쳐 각 쿼리의 정답을 출력하여라.
만약 가능하다면 "YES", 불가능하다면 "NO"를 출력하여라. (쌍따옴표 제외)
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | N, Q <= 5,000, B1 + B2 + ... + BN <= 5,000 |
| #2 | 5점 | N <= 5,000, B1 + B2 + ... + BN <= 5,000 |
| #3 | 15점 | N <= 100,000, Ci <= 20, Ai,j <= 20 |
| #4 | 75점 | 추가적인 제한이 없다. |
예제 #1
5
1 2 3 4
2 2 3
1 1
1 1
1 3
1 4
4
2 4
4 2
1 5
5 3
YES
NO
NO
YES
예제 #2
5
2 3 1 3
1 3
1 2
1 1
1 3
1 2
4
1 3
3 1
4 3
2 5
NO
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
YES
NO
YES
로그인해야 코드를 작성할 수 있어요.