gGames

엘프의 나라는 탈락 토너먼트를 개최할 계획이며, 참가하고 싶어 하는 엘프가 $2^{N}$명 있다. 토너먼트가 시작될 때, 이들에게 1부터 $2^{N}$까지의 고유한 ID 번호가 주어지며, 엘프 대통령은 이들을 어떤 순서로 한 줄로 세운다.

토너먼트는 두 엘프 사이의 일련의 경기로 이루어지며, 모든 경기에는 승자 한 명과 패자 한 명이 있다(무승부는 없다). 첫 번째 라운드에서는 줄의 첫 번째 엘프가 두 번째 엘프와 경기하고, 세 번째 엘프가 네 번째 엘프와 경기하는 식으로 계속된다. 첫 번째 라운드가 끝나면 패배한 2^{N-1}명의 엘프는 줄을 떠나고, 승리한 2^{N-1}명의 엘프는 있던 자리에 남는다. 그러면 남은 엘프들은 같은 방식으로 두 번째 라운드를 치른다. 줄에 남은 첫 번째 엘프가 남은 두 번째 엘프와 경기하고, 남은 세 번째 엘프가 남은 네 번째 엘프와 경기하는 식으로 계속된다. N번의 라운드가 끝나면 엘프가 단 한 명만 남으며, 그 엘프가 우승자이다.

엘프 중 M명은 예민하며, 이는 경기 중 친구와 경기를 치러야 하면 매우 슬퍼한다는 뜻이다. 구체적으로, i번째 엘프는 첫 $K_{i}$번의 라운드에서 친구와 경기를 치러야 하면 슬퍼한다. (친구 관계가 반드시 상호적인 것은 아니라는 점에 유의하라. 한 엘프가 다른 엘프를 친구로 여겨도, 그 다른 엘프가 반드시 해당 엘프를 친구로 여기는 것은 아니다.)

엘프 대통령은 토너먼트에서 무슨 일이 일어나더라도 어떤 엘프도 슬퍼하지 않도록 보장할 수 있게, $2^{N}$명인 모든 엘프의 초기 위치를 지정하는 방법이 있는지 알고 싶어 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 200. 0 ≤ M ≤ $2^{N}$. 1 ≤ $E_{i}$ ≤ $2^{N}$. 1 ≤ $K_{i}$ ≤ N. M ≤ sum($B_{i}$) ≤ min(2 * M, $2^{N}$).

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 3.

큰 데이터 세트 (테스트 세트 2 - 비공개)

N = 4.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 M이 있는 한 줄로 시작하고, 그 뒤에 각각 두 줄로 이루어진 M개의 집합이 주어진다. 각 집합의 첫 번째 줄에는 한 엘프에 대한 정수 $E_{i}$, $K_{i}$, $B_{i}$가 주어지고, 두 번째 줄에는 그 엘프의 친구들의 $B_{i}$개 정수 ID 번호가 주어진다.

각 테스트 케이스마다 "Case #x: "를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이며, 그 뒤에 YES 또는 NO가 온다.