아무나 풀어주세요

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

요약
수열 A에서 시작해 뒤에 숫자를 붙이되 짝수를 붙일 때는 마지막 세 수를 오름차순으로 정리한 뒤 붙이는 규칙으로 수열 B를 만들 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
동적 계획법, 그리디
정답자
아직 제출이 없습니다

문제

건모는 수열을 가지고 놀다가 재밌는 게임을 하기로 결정했다.

게임은 다음과 같이 진행된다.

  1. 건모는 처음에 수열 AA를 가지고 시작한다.
  2. 11부터 99 사이 원하는 숫자를 수열 맨 뒤에 추가한다.
    • 단, 추가하려는 수가 짝수인 경우 수열의 마지막 수 세 개를 오름차순으로 정렬한 뒤 추가해야 한다.
  3. 수열 BB를 만들게 되면, 건모는 게임에서 승리하고, 어떻게 해도 만들 수 없다면 게임에서 패배한다.

건모는 되면 한다 라는 마인드를 가지고 있기 때문에 불가능하다면 시도조차 하지 않을 생각이다.

건모가 게임에서 승리하는지 아닌지를 출력해라.

입력

첫째 줄에 테스트 케이스의 수를 나타내는 정수 TT가 주어진다. (1≤T≤5,000)(1\le T\le 5\\, 000)

둘째 줄부터 테스트 케이스 TT개가 주어진다.

각 테스트 케이스는 다음과 같은 형태로 이루어져 있다.

테스트 케이스 첫 줄에 수열 AA의 길이를 뜻하는 NN, 수열 BB의 길이를 뜻하는 MM이 공백으로 구분되어 주어진다. (3≤N≤M≤5,000)(3\le N\le M\le 5\\, 000)

테스트 케이스 둘째 줄에 A_1A\_1, A_2A\_2, ⋯\cdots, A_NA\_N이 공백으로 구분되어 주어진다. (1≤A_i≤9)(1\le A\_i\le 9)

테스트 케이스 셋째 줄에 B_1B\_1, B_2B\_2, ⋯\cdots, B_MB\_M이 공백으로 구분되어 주어진다. (1≤B_i≤9)(1\le B\_i\le 9)

모든 테스트 케이스에서 MM의 합은 15,00015\\, 000을 넘지 않는다.

주어지는 모든 수는 정수이다.

출력

각 테스트 케이스별로 정답을 한 줄에 하나씩 출력한다.

건모가 게임에서 승리한다면 YES를, 패배한다면 NO를 출력해야 한다.

출력 시 대소문자를 구분하지 않아도 된다. 예를 들어, 건모가 게임에서 승리한 경우 yEs, yes, YES 모두 정답으로 인정된다.

예제1

  1. 예제 1

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