검술의 대가

당신은 다음 검술의 대가가 되기를 열망하는 결투가이다. 모든 상대를 상대로 승리할 때까지 상대들과 결투하여 이 칭호를 얻고자 한다. 모든 상대는 언제든 결투할 수 있으며, 상대들끼리는 결투하지 않는다.

당신을 포함한 각 결투가는 적어도 하나의 공격과 적어도 하나의 방어를 알고 있다. 세상에는 공격과 방어의 쌍이 최대 P개 있다. i번째 방어는 i번째 공격만 막으며, i번째 공격은 i번째 방어로만 막을 수 있다. 어떤 결투가도 알지 못하는 공격 및/또는 방어가 있을 수 있다. 당신은 자신이 아는 공격이나 방어를 원하는 만큼 여러 번 사용할 수 있으며, 이를 사용해도 "소모"되지 않는다.

상대 한 명과 벌이는 각 결투의 규칙은 다음과 같다.

• 검술의 대가를 열망하는 당신이 항상 먼저 공격한다. 당신이 아는 공격 하나를 선택한다. 상대가 그에 대응하는 방어를 알고 있다면, 그 방어를 사용할지 선택할 수 있다. 상대가 그 방어를 알지 못하거나 사용하지 않기로 선택하면 방어하지 않는다.

• 그다음 상대가 자신이 아는 공격 하나를 선택한다. 당신이 그에 대응하는 방어를 알고 있다면, 그 방어를 사용할지 선택할 수 있다. 그 방어를 알지 못하거나 사용하지 않기로 선택하면 방어하지 않는다.

• 당신은 성공적으로 방어했고 상대는 방어하지 못했다면 결투에서 승리한다! 그렇지 않으면 승리하지 못하지만, 검술의 대가가 되기 위한 여정은 계속할 수 있다.

이전 결투의 결과와 관계없이 같은 상대와 여러 번 결투하는 것을 포함하여 원하는 만큼 결투할 수 있다. 완전한 결투 일정을 미리 정할 필요는 없으며, 이미 일어난 일을 바탕으로 다음 결정을 내릴 수 있다. 모든 상대를 상대로 적어도 한 번씩 승리하면 검술의 대가가 된다!

당신은 특히 학습이 빠르다. 각 결투가 끝난 뒤에는 결투 결과와 관계없이 상대가 사용한 공격과 방어(사용했다면)를 자신이 아는 공격과 방어의 집합에 추가할 수 있다. (상대가 당신이 모르는 방어를 사용하더라도 결투 도중에는 배우지 못하므로, 같은 결투에서 상대의 공격에 그 방어를 사용할 수 없다는 점에 유의하라.) 이러한 이점은 당신에게만 있으며, 상대들이 아는 공격과 방어는 절대 바뀌지 않는다.

또한 어떤 상대를 상대로 승리한 뒤 다음 결투를 시작하기 전에, 그 상대는 자신이 알지만 당신은 아직 알지 못하는 모든 공격과 방어를 당신에게 가르쳐 준다. (당신에게 패한 뒤에는 당신이 결국 검술의 대가가 되는 편이 그 상대의 체면에도 더 좋다!)

당신은 각 상대가 어떤 공격과 방어를 아는지 알고 있다. 최적으로 선택한다면, 상대들이 어떤 선택을 하든 당신이 검술의 대가가 되는 것을 보장할 수 있는가?

제한

1 ≤ T ≤ 100. 2 ≤ N ≤ 1000. 1 ≤ P ≤ 1000. 모든 i에 대해, 1 ≤ $Attacks_{i}$ ≤ P. 모든 i에 대해, 1 ≤ $Defenses_{i}$ ≤ P. 모든 i와 j에 대해, 1 ≤ $A_{ij}$ < $A_{i(j+1)}$ ≤ P. 모든 i와 j에 대해, 1 ≤ $D_{ij}$ < $D_{i(j+1)}$ ≤ P. 모든 i에 대한 $Attacks_{i}$의 합과 모든 $Defenses_{i}$의 합을 더한 값은 50000을 초과하지 않는다. 시간 제한: 테스트 세트당 10초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

모든 i에 대해, $A_{i1}$ = 1. (당신을 포함한 모든 결투가가 공격 1을 알고 있다.) 모든 i에 대해, $D_{i1}$ = 1. (당신을 포함한 모든 결투가가 방어 1을 알고 있다.)

테스트 세트 2 (비공개)

추가 제한 없음.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

• 각 테스트 케이스는 두 정수 N과 P가 있는 한 줄로 시작한다. 이들은 당신을 포함한 결투가의 수와 세상에 존재하는 공격과 방어 쌍의 최대 개수이다.

• 그다음 각각 세 줄로 이루어진 N개의 묶음이 주어진다. 이 중 i번째 묶음은 결투가 한 명을 나타내며, 특히 첫 번째 묶음은 당신을 나타낸다. 각 묶음의 구조는 다음과 같다.

• 두 정수 $Attacks_{i}$와 $Defenses_{i}$가 있는 한 줄: 각각 i번째 결투가가 아는 서로 다른 공격과 방어의 개수이다.

• 오름차순으로 정렬된 $Attacks_{i}$개의 서로 다른 정수 $A_{ij}$가 있는 한 줄: i번째 결투가가 아는 공격들의 식별자이다.

• 오름차순으로 정렬된 $Defenses_{i}$개의 서로 다른 정수 $D_{ij}$가 있는 한 줄: i번째 결투가가 아는 방어들의 식별자이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, 문제 설명에 나온 대로 당신이 검술의 대가가 되는 것을 보장할 수 있다면 y는 YES이며, 그렇지 않으면 NO이다.

마지막 네 개의 예제 케이스는 테스트 세트 1에는 나오지 않는다는 점에 유의하라.

예제 케이스 #1에서 상대가 계속 방어 1과 공격 1을 선택하면 결투에서 승리할 수 없다. 상대가 언젠가 공격 2을 선택하거나 방어 1를 사용하지 않기로 선택한다는 보장은 없으므로, 당신이 검술의 대가가 되는 것을 보장할 수 없다.

예제 케이스 #2에서 당신은 공격 1과 방어 2를 알고 있고, 유일한 상대는 공격 2과 방어 1를 알고 있다. 다음 전략을 사용하면 당신이 검술의 대가가 되는 것이 보장된다.

• 첫 결투에서 당신은 공격 1을 선택해야 하며, 상대는 방어 1로 방어할 수 있다. 그다음 상대는 반드시 공격 2을 선택해야 하며, 당신은 방어 2를 선택해야 한다.

• 상대가 방어하지 않았다면 당신이 승리했으며, 이제 검술의 대가이다.

• 그렇지 않으면 승리하지 못하지만, 결투가 끝난 뒤 공격 2과 방어 1를 배운다. 그런 다음 그 상대와 두 번째 결투를 시작한다. 이번에는 공격 2을 선택한다. 상대는 이를 방어할 수 없다. 다시 한번 상대는 반드시 공격 2을 선택해야 하며, 당신은 방어 2를 선택해야 한다. 당신은 승리했으며, 이제 검술의 대가이다.

예제 케이스 #3의 첫 결투에서 상대가 항상 공격 4을 선택하면, 그 공격에 대한 방어를 아무도 알지 못하므로 당신은 절대 방어할 수 없다. 따라서 당신이 검술의 대가가 될 방법은 전혀 없다. 세상에 존재하지만 이 문제의 어느 결투가도 알지 못하는 공격 및/또는 방어가 있을 수 있다는 점에 유의하라.

예제 케이스 #4에는 모든 방어를 아는 상대가 있으므로, 그 상대를 상대로 언젠가 승리하리라고 보장할 수 없다. (상대가 친절을 베풀어 방어하지 않아야만 한다!)

다음은 예제 케이스 #5에서 승리를 보장하는 한 가지 전략이다.

• 첫 번째 상대와 결투한다. 당신은 공격 1을 선택해야 하며, 상대는 방어할 수 없다. 여기서는 상대가 공격 2을 선택한다고 가정하고 진행한다. (공격 3을 선택한다면, 이와 동형인 전략이 통한다.) 당신은 방어할 수 없고 결투에서 승리하지 못하지만, 공격 2을 배운다.

• 세 번째 상대와 결투하고, 공격 2과 방어 4를 사용하여 확실히 승리한다. 공격 4(앞으로 절대 사용하지 않을 공격)과 방어 1 및 3를 배운다.

• 두 번째 상대와 결투하고 공격 2을 사용한다. 방어 2를 배우는 것이 보장된다. 상대가 그것을 당신의 공격에 사용하거나, 사용하지 않아서 당신이 승리하고 상대의 모든 공격과 방어를 배우기 때문이다.

• 첫 번째 상대와 다시 결투하고 공격 1을 선택한다. 이제 상대가 어느 공격을 사용하든 방어할 수 있으므로 승리한다. 공격 3을 배운다.

• 이전에 두 번째 상대를 상대로 아직 승리하지 않았다면, 공격 3을 사용하여 그 상대와 다시 결투한다.