보물

오래된 지도를 따라가던 중, 당신은 무시무시한 해적 Larry의 비밀 보물 창고를 우연히 발견했다!

보물 창고에는 잠긴 상자가 N개 있으며, 각 상자는 특정 유형의 열쇠로만 열 수 있다. 또한 열쇠를 한 번 사용해 상자를 열면 다시는 사용할 수 없다. 물론 모든 상자 안에서는 많은 보물을 찾을 수 있으며, 다른 상자를 여는 데 사용할 수 있는 열쇠를 하나 이상 찾을 수도 있다. 하나의 상자에는 같은 유형의 열쇠가 여러 개 들어 있을 수 있으며, 열쇠는 몇 개든 소지할 수 있다.

당신은 이미 적어도 하나의 열쇠를 가지고 있으며, 지도에는 여러 상자 안에서 어떤 다른 열쇠를 찾을 수 있는지가 적혀 있다. 이 모든 정보를 바탕으로 모든 상자를 여는 방법을 알아낼 수 있는가?

예를 들어, 보물 창고가 아래에 설명된 네 개의 상자로 이루어져 있고, 처음에 1 유형의 열쇠를 정확히 하나 가지고 있었다고 하자.

Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             |  1                       |  None
2             |  1                       |  1, 3
3             |  2                       |  None
4             |  3                       |  2

이 예제에서는 상자를 2, 1, 4, 3 순서로 열면 모든 상자를 열 수 있다. 가장 먼저 #1 상자를 열면 유일한 열쇠를 다 써 버리므로 더 진행할 수 없게 된다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 25. 1 ≤ K. 모든 열쇠 유형은 1 이상 200 이하의 정수이다.

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

1 ≤ N ≤ 20. 각 테스트 케이스에서 열쇠는 모두 합쳐 최대 40개이다.

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

1 ≤ N ≤ 200. 각 테스트 케이스에서 열쇠는 모두 합쳐 최대 400개이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 양의 정수 K와 N이 포함된 한 줄로 시작하며, 각각 처음에 가지고 있는 열쇠의 수와 열어야 하는 상자의 수를 나타낸다.

이어서 처음에 가지고 있는 열쇠의 유형을 나타내는 K개의 정수가 한 줄에 주어진다.

그다음에는 각각 하나의 상자를 나타내는 N개의 줄이 주어진다. 각 줄은 정수 $T_{i}$와 $K_{i}$로 시작하며, 각각 상자를 여는 데 필요한 열쇠의 유형과 상자 안에 있는 열쇠의 수를 나타낸다. 이 두 정수 뒤에는 상자 안에 들어 있는 열쇠의 유형을 나타내는 정수 $K_{i}$개가 더 주어진다.

각 테스트 케이스마다 "Case #x: $C_{1}$ $C_{2}$ ... $C_{N}$"이 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), $C_{i}$은 열어야 할 $i^{th}$ 상자의 인덱스(1부터 시작)를 나타낸다.

모든 상자를 여는 방법이 여러 가지라면 "lexicographically smallest" 방법을 선택한다. 다시 말해, $C_{1}$을 가능한 한 작게 만들어야 하며, $C_{1}$을 가능한 한 작게 만드는 방법이 여러 가지라면 $C_{2}$을 가능한 한 작게 만드는 방법을 선택하고, 이후에도 같은 방식으로 선택한다.

모든 상자를 열 방법이 없다면 대신 "Case #x: IMPOSSIBLE"이 포함된 한 줄을 출력한다.