Copper Golem and Chests

시간 제한1초메모리 제한1024 MB

요약
각 상자가 다른 상자로 아이템을 보내는 순열이 주어질 때, 이동을 반복해 아이템이 상자 번호 순서대로 정리될 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
그래프, 유니온 파인드, 구현, 배열
정답자
아직 제출이 없습니다

문제

NN개의 아이템과 무한개의 아이템을 보관할 수 있는 MM개의 상자가 주어진다. 각 아이템은 11부터 NN까지 순서대로 번호가 매겨져 있고, 각 상자는 11부터 MM까지 순서대로 번호가 매겨져 있다. 최초에 i(1≤i≤N)i(1\le i\le N)번 아이템은 A_iA\_i번 상자에 보관되어 있고, j(1≤j≤M)j(1≤j≤M)번 상자 위에는 정수 B_jB\_j가 적힌 표지판이 설치되어있다. 이때, 표지판에 적힌 수는 서로 다르다.

동희는 아이템을 정리하기 위해 구리 골렘을 소환했다. 구리 골렘에게 다음 작업을 명령할 수 있다.

  • 동희가 i(1≤i≤N)i(1≤i≤N)를 선택한다. 구리 골렘은 ii번 아이템을 상자에서 꺼내고, 해당 상자 위에 설치된 표지판에 적힌 수가 XX일때, ii번 아이템을 XX번 상자에 보관한다.

한편, 다음 조건을 만족하면 아이템들이 잘 정리되었다고 본다.

  • 1≤i≤j≤N1\le i\le j\le N인 모든 (i,j)(i,j) 쌍에 대해서 ii번 아이템이 보관된 상자의 번호가 jj번 아이템이 보관된 상자의 번호보다 작거나 같다.

동희는 아이템을 찾기 위해 상자를 여러 번 뒤지는 것을 싫어하기 때문에, 아이템들이 가능한 한 잘 정리되었으면 한다. 구리 골렘에게 00번 이상 작업을 명령해서 아이템들이 잘 정리되도록 만들 수 있는지 판단하는 프로그램을 작성해 보자.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. (1≤T≤200,000)(1≤T≤200\\, 000)

각 테스트 케이스의 첫째 줄에 NN과 MM이 공백으로 구분되어 주어진다. (1≤N,M≤200,000)(1≤N,M≤200\\, 000)

각 테스트 케이스의 둘째 줄에 NN개의 정수 A_1,A_2,⋯ ,A_NA\_1,A\_2,\cdots ,A\_N이 공백으로 구분되어 주어진다. (1≤A_i≤M)(1≤A\_i≤M)

각 테스트 케이스의 셋째 줄에 MM개의 서로 다른 정수 B_1,B_2,⋯ ,B_MB\_1,B\_2,\cdots ,B\_M이 공백으로 구분되어 주어진다. (1≤B_i≤M)(1≤B\_i≤M)

모든 테스트 케이스에서 NN의 합과 MM의 합은 각각 200,000200\\, 000을 초과하지 않는다.

출력

각 테스트 케이스마다 아이템들을 잘 정리할 수 있다면 YES를, 정리할 수 없다면 NO를 출력한다.

힌트

마인크래프트에 등장하는 구리 골렘의 작동 방식과는 다를 수 있다.

예제1

  1. 예제 1

    입력
    5
    5 5
    1 3 1 2 5
    4 1 5 2 3
    5 5
    1 3 1 5 2
    4 1 5 2 3
    4 2
    1 2 1 2
    2 1
    2 2
    2 1
    1 2
    1 1
    1
    1
    
    예상 출력
    YES
    NO
    YES
    NO
    YES