시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 81 25 23 35.938%

문제

태현이는 네 명의 친구와 5대 5 미팅에 참여하게 되었다. 미팅 자리에서 각 사람의 소개가 끝나고, 각자의 짝을 정할 시간이 되었는데, 태현이가 다음과 같은 방법을 제안하였고, 모두 이에 찬성하였다.

  1. 태현이가 1번, 나머지남학생이 2~5번, 여학생이 6~10번이라고 하자.
  2. 우선 각자 상대방 5명에 대한 선호도 순위를 매겨서 쓴다. 이 때 2명 이상의 상대에게 같은 선호도를 적용해도 안 되며, 5명의 모든 상대에 대해서 순위를 매겨야 한다. 태현이의 선호도는 6 7 8 9 10 이다. 즉 6번 여학생을 가장 좋아하고, 차례로 7~10번 여학생을 좋아한다.
  3. 6번 여학생부터 선호도 리스트를 보면서 가장 좋아하는 남학생에게 프러포즈를 한다. 이 때 그 남학생이 자신에게 퇴짜를 놓은 적이 있다면 그 다음 순위의 남학생에게 프러포즈를 한다.
  4. 남학생은 프러포즈를 받을지 퇴짜를 놓을지를 결정하는데, 현재 자신에게 짝이 없으면 무조건 프러포즈를 받아들여서 그 여학생과 잠정적으로 짝이 된다. 하지만 현재 짝이 있으면 두 명에 대한 자신의 선호도를 비교해서 더 좋아하는 여학생과 잠정적으로 짝이 되고 다른 여학생에게는 퇴짜를 놓게 된다.
  5. 이렇게 해서 10번까지 짝짓기를 하는 것을 한 라운드라고 하면, 퇴짜를 받은 여학생들만 다음 라운드에 다시 짝짓기에 참여한다.
  6. 모든 학생들이 잠정적으로 짝을 찾을 때까지 이 과정을 반복하며 마지막에 서로의 짝이 최종 짝이 된다.

각자 자기가 선호하는 리스트를 적어서 주선자인 태현이에게 주었다. 태현이는 종이와 연필을 갖고 옆 테이블로 자리를 옮겨서 위의 알고리즘을 적용하였다. 문득 태현이는 자신의 선호도를 바꾸면 좀 더 좋아하는 여학생과 짝이 될 수 있지 않을까 하는 고민에 빠졌다. 즉, 태현이의 선호도는 6 7 8 9 10이지만, 이를 적지 않고 다른 선호도를 적으면 더 좋아하는 여학생과 짝이 될 수 있지 않을까 하는 고민에 빠졌다.

각 학생이 적어 낸 선호도 리스트가 주어졌을 때, 태현이가 자신의 선호도를 적당히 바꿔 적어서 원래 선호도 리스트로 맺어지는 여학생보다 더 좋아하는 여학생과 맺어질 수 있는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 데이터의 개수 T(1≤T≤10)가 주어진다. 각각의 테스트 데이터는 9줄로 이루어진다. 앞의 네 줄은 차례로 2~5번 학생의 선호도 목록이고, 뒤의 다섯 줄은 차례로 6~10번 여학생의 선호도 목록이다. 태현이는 6 7 8 9 10이며, 이는 입력으로는 주어지지 않는다.

출력

T개의 줄에 차례로 각 데이터의 답을 출력한다. 가능할 경우에는 YES를, 불가능할 경우에는 NO를 출력한다.

예제 입력

3
10 9 6 7 8
8 10 7 9 6
9 7 6 8 10
8 10 6 9 7
2 3 1 4 5
5 1 2 3 4
3 2 1 4 5
2 3 1 5 4
5 3 4 1 2
8 7 6 10 9
7 8 10 9 6
6 7 9 8 10
7 9 8 6 10
5 1 3 2 4
3 1 4 5 2
1 3 5 4 2
2 4 3 1 5
1 2 3 5 4
6 8 9 7 10
9 8 7 6 10
8 7 10 9 6
8 9 6 7 10
5 1 4 3 2
5 3 4 1 2
3 5 1 4 2
1 3 4 5 2
5 1 3 2 4

예제 출력

NO
YES
YES

힌트