새끼 고양이의 집 (라지)

문제

새끼 고양이 몇 마리를 입양해서 이제 고양이 집을 짓는다. 집을 밖에서 보면 꼭짓점이 $N$ 개인 볼록 다각형이다. 집 안은 내벽 $M$ 개가 여러 방으로 나눈 구조다. 내벽은 두 꼭짓점을 직선으로 잇는다. 두 내벽이 서로 교차하는 일은 없지만, 한 꼭짓점에 내벽 여러 개가 닿을 수는 있다.

꼭짓점마다 개박하로만 만든 기둥을 세운다. 고양이는 자기가 있는 방에 닿아 있는 기둥이라면 어느 것이든 가지고 놀 수 있다.

개박하 맛은 여러 가지를 쓰려고 한다. 기둥 하나에는 맛 하나만 쓰지만, 기둥마다 다른 맛을 써도 된다. 문제는 어떤 방에서 집에 있는 맛 전부에 닿을 수 없으면 그 방의 고양이가 소외감을 느낀다는 점이다. 그래서 기둥에 맛을 배정할 때 다음 두 조건을 지켜야 한다.

(a) 어느 방에서든 모든 맛에 닿을 수 있다. (b) 쓰는 맛의 종류를 최대한 많게 한다.

집이 쓸 수 있는 맛의 최대 개수 $C$ 를 구한다. 배정 자체는 출력하지 않는다.

아래 그림은 꼭짓점이 8개인 집에서 맛 세 가지(빨강, 초록, 파랑 점)를 쓰면서도 모든 방이 세 맛에 다 닿는 예다. 위쪽 벽의 왼쪽 꼭짓점에서 시작해 시계 방향으로 보면 초록, 파랑, 빨강, 빨강, 파랑, 초록, 파랑, 빨강 순서다.

입력

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

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

꼭짓점 번호는 시계 방향으로 $1, 2, \dots, N$ 이므로 $i$ 번째 내벽은 꼭짓점 $U_i$ 와 꼭짓점 $V_i$ 를 잇는다.

제한

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

출력

각 테스트 케이스마다 Case #x: C 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $C$ 는 그 집이 쓸 수 있는 개박하 맛의 최대 개수다. 이 수만 출력하고, 기둥마다 어떤 맛을 배정했는지는 출력하지 않는다.