새끼 고양이의 집 (작은 입력)

문제

새끼 고양이를 여러 마리 입양해서 고양이 집을 지으려고 한다. 집의 바깥 윤곽은 꼭짓점이 $N$ 개인 볼록 다각형이고, 내부는 꼭짓점끼리 직선으로 잇는 벽 $M$ 개로 여러 개의 방으로 나뉜다. 두 벽이 꼭짓점이 아닌 곳에서 만나는 일은 없지만, 한 꼭짓점에 여러 벽이 닿을 수는 있다.

꼭짓점마다 캣닢으로 기둥을 하나씩 세운다. 고양이는 자기가 있는 방에 닿아 있는 기둥이라면 무엇이든 가지고 놀 수 있다.

캣닢은 맛이 여러 가지다. 기둥 하나에는 맛을 한 가지만 쓰지만, 기둥마다 다른 맛을 써도 된다. 문제는 어떤 방에서 집에 쓰인 맛 전부에 닿을 수 없으면 그 방의 고양이가 서운해한다는 점이다.

꼭짓점마다 캣닢 맛을 정해서 (가) 모든 방에서 모든 맛에 닿을 수 있고, (나) 쓰는 맛의 가짓수가 최대가 되도록 하라.

아래 그림은 팔각형 집에 세 가지 맛(빨강, 초록, 파랑 점)을 배치해 모든 방의 고양이를 만족시킨 예다. 위쪽 벽의 왼쪽 끝에서 시작해 시계 방향으로 초록, 파랑, 빨강, 빨강, 파랑, 초록, 파랑, 빨강이다. 조건을 만족하는 배치는 여러 개일 수 있고, 그림은 그중 하나다.

입력

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

각 테스트 케이스는 세 줄이다. 첫 줄에 꼭짓점의 수 $N$ 과 내부 벽의 수 $M$ 이 공백으로 구분되어 주어진다. 둘째 줄에는 각 벽이 시작하는 꼭짓점 $U_1, U_2, \dots, U_M$ 이 공백으로 구분되어 주어진다. 셋째 줄에는 각 벽이 끝나는 꼭짓점 $V_1, V_2, \dots, V_M$ 이 같은 방식으로 주어진다.

꼭짓점에 시계 방향으로 $1$ 부터 $N$ 까지 번호를 붙였을 때, $i$ 번째 벽은 꼭짓점 $U_i$ 와 $V_i$ 를 잇는다.

제한

$1 \le T \le 100$
$4 \le N \le 8$
$1 \le M \le N - 3$
모든 $i$ 에 대해 $1 \le U_i < V_i \le N$
내부 벽끼리는 꼭짓점 $N$ 개에서만 서로 닿는다.
내부 벽은 꼭짓점 $N$ 개에서만 집의 바깥 윤곽에 닿는다.

출력

각 테스트 케이스마다 두 줄을 출력한다.

첫 줄에는 Case #x: C를 출력한다. $x$ 는 테스트 케이스 번호이고, $C$ 는 쓸 수 있는 캣닢 맛의 최대 가짓수다.

둘째 줄에는 꼭짓점 $i$ 에 배정한 맛의 번호 $y_i$ 를 공백으로 구분해 $N$ 개 출력한다. 각 $y_i$ 는 $1$ 이상 $C$ 이하의 정수다.

맛 $C$ 가지를 모두 쓰면서 조건을 만족하는 배정이 여러 개면, 수열 $y_1\ y_2\ \dots\ y_N$ 이 사전순으로 가장 앞서는 것 하나만 출력한다.