레이팅 미적용무텔(mootel, 모텔과 비슷하지만 사람 대신 소 손님이 묵는 곳)의 무질서한 구조 때문에, 농부 존은 무텔 관리인 역할을 맡아 축사의 질서를 되찾기로 결심했다.
각 무텔에는 \(1\)부터 \(N\)까지 번호가 매겨진 \(N\)개의 축사(\(1 \le N \le 10^5\))와 축사 쌍들을 양방향으로 연결하는 \(M\) (\(0 \le M \le 10^5\))개의 복도가 있다. \(i\)번째 축사는 색 \(C_i\)로 칠해져 있고 처음에 색 \(S_i\)의 열쇠 하나가 들어 있다. 농부 존은 소들을 달래고 축사의 질서를 되찾기 위해 열쇠들을 재배치해야 한다.
농부 존은 열쇠를 하나도 들지 않은 채 축사 \(1\)에서 시작하며, 다음 행동 중 하나를 반복해서 할 수 있다:
- 현재 있는 축사의 열쇠를 집는다. 농부 존은 한 번에 여러 개의 열쇠를 들 수 있다.
- 들고 있는 열쇠 하나를 현재 있는 축사에 내려놓는다. 한 축사에 여러 개의 열쇠가 있을 수 있다.
- 복도를 통해 이동하여 축사 \(1\)에 들어간다.
- 복도를 통해 이동하여 축사 \(1\) 이외의 축사에 들어간다. 이는 들어가려는 축사와 같은 색의 열쇠를 현재 들고 있을 때만 가능하다.
안타깝게도 열쇠들이 의도된 위치에 있지 않은 것 같다. 농부 존의 무텔의 질서를 되찾으려면, \(i\)번째 축사에 색 \(F_i\)의 열쇠 하나가 있어야 한다. \(S\)가 \(F\)의 순열임이 보장된다.
\(T\)개의 서로 다른 무텔(\(1 \le T \le 100\))에 대해, 농부 존은 축사 \(1\)에서 시작하여 모든 열쇠를 적절한 위치에 놓고 축사 \(1\)로 돌아와야 한다. \(T\)개의 무텔 각각에 대해, 이것이 가능한지 답하라.
출제자: Eric Yachbes
배점
- 테스트 케이스 3-6은 \(N,M\le 8\)을 만족한다.
- 테스트 케이스 7-10은 \(C_i=F_i\)를 만족한다.
- 테스트 케이스 11-18은 추가 제약 조건이 없다.
출제자: Eric Yachbes
첫째 줄에 무텔(테스트 케이스)의 개수 \(T\)가 주어진다.
각 테스트 케이스 앞에는 빈 줄이 하나 있다. 그런 다음, 각 테스트 케이스의 첫째 줄에 두 정수 \(N\)과 \(M\)이 주어진다.
각 테스트 케이스의 둘째 줄에 \(N\)개의 정수가 주어진다. 이 줄의 \(i\)번째 정수 \(C_i\)는 축사 \(i\)의 색이 \(C_i\)임을 의미한다 (\(1 \le C_i \le N\)).
각 테스트 케이스의 셋째 줄에 \(N\)개의 정수가 주어진다. 이 줄의 \(i\)번째 정수 \(S_i\)는 축사 \(i\)에 처음에 색 \(S_i\)의 열쇠가 있음을 의미한다 (\(1 \le S_i \le N\)).
각 테스트 케이스의 넷째 줄에 \(N\)개의 정수가 주어진다. 이 줄의 \(i\)번째 정수 \(F_i\)는 축사 \(i\)에 색 \(F_i\)의 열쇠가 있어야 함을 의미한다 (\(1 \le F_i \le N\)).
각 테스트 케이스에서 다음 \(M\)개의 줄이 이어진다. 이 중 \(i\)번째 줄에는 서로 다른 두 정수 \(u_i\)와 \(v_i\) (\(1 \le u_i, v_i \le N\))가 주어진다. 이는 축사 \(u_i\)와 \(v_i\) 사이에 복도가 존재함을 나타낸다. 중복되는 복도는 없다.
모든 무텔에 대한 \(N\)의 합은 \(10^5\)를 넘지 않고, 모든 무텔에 대한 \(M\)의 합은 \(2\cdot 10^5\)를 넘지 않는다.
각 무텔에 대해, 농부 존이 각 축사 \(i\)에 색 \(F_i\)의 열쇠를 되돌려 놓고 축사 \(1\)로 돌아올 수 있는 방법이 존재하면 YES를 새 줄에 출력한다. 그렇지 않으면 NO를 새 줄에 출력한다.
2
5 5
4 3 2 4 3
3 4 3 4 2
2 3 4 4 3
1 2
2 3
3 1
4 1
4 5
4 3
3 2 4 1
2 3 4 4
4 2 3 4
4 2
4 1
4 3YES
NOFor the first test case, here is a possible sequence of moves:
Current stall: 1. Keys held: []. Keys in stalls: [3, 4, 3, 4, 2]
(pick up key of color 3)
Current stall: 1. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(move from stall 1 to 2, allowed since we have a key of color C_2=3)
Current stall: 2. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(pick up key of color 4)
Current stall: 2. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(move from stall 2 to 1 to 4 to 5, allowed since we have keys of colors C_4=4 and C_5=3)
Current stall: 5. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(pick up key of color 2 and place key of color 3)
Current stall: 5. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(move from stall 5 to 4 to 1 to 3, allowed since we have keys of colors C_4=4 and C_3=2)
Current stall: 3. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(pick up key of color 3 and place key of color 4)
Current stall: 3. Keys held: [2, 3]. Keys in stalls: [x, x, 4, 4, 3]
(move from stall 3 to stall 2 and place key of color 3)
Current stall: 2. Keys held: [2]. Keys in stalls: [x, 3, 4, 4, 3]
(move from stall 2 to stall 1 and place key of color 2)
Current stall: 1. Keys held: []. Keys in stalls: [2, 3, 4, 4, 3]
For the second test case, there exists no way for FJ to return a key of color
\(F_i\) to each stall \(i\) and end back at stall \(1\).
5
2 0
1 2
2 2
2 2
2 1
1 1
2 1
2 1
1 2
2 1
1 1
2 1
1 2
1 2
2 1
1 1
1 2
2 1
1 2
5 4
1 2 3 4 4
2 3 5 4 2
5 3 2 4 2
1 2
1 3
1 4
4 5YES
YES
NO
YES
NO