House of Kittens (Large)

You adopted a few kittens, and now you are building a house for them. From the outside the house is a convex polygon with $N$ vertices. Inside, $M$ interior walls divide it into rooms, and each interior wall is a straight segment between two vertices. No two interior walls cross, but several walls may touch the same vertex.

At every vertex you build a pillar made entirely of catnip. A kitten can play with any pillar that touches the room it is in.

You want to use several flavors of catnip. One pillar uses a single flavor, and different pillars may use different flavors. The problem is that if some room cannot reach every flavor in the house, the kittens in that room feel left out. So the assignment of flavors to pillars has to satisfy both of these conditions.

(a) Every flavor is reachable from every room. (b) The number of flavors used is as large as possible.

Find $C$, the largest number of flavors the house can use. You do not print the assignment itself.

The picture below shows an 8-sided house that uses three flavors (the red, green, and blue dots) while every room still reaches all three. Starting at the left vertex of the top wall and going clockwise, the flavors are green, blue, red, red, blue, green, blue, red.

The first line contains the number of test cases, $T$. $T$ test cases follow.

Each test case consists of three lines. The first line contains the number of vertices $N$ and the number of interior walls $M$. The second line contains $M$ space-separated integers $U_1, U_2, \dots, U_M$, the vertex where each interior wall begins. The third line contains $M$ space-separated integers $V_1, V_2, \dots, V_M$, the vertex where each interior wall ends.

The vertices are numbered $1, 2, \dots, N$ in clockwise order, so interior wall $i$ joins vertex $U_i$ and vertex $V_i$.

Limits

• $1 \le T \le 100$
• $4 \le N \le 2000$
• $1 \le M \le N - 3$
• $1 \le U_i < V_i \le N$ for every $i$
• Interior walls touch each other only at the $N$ vertices.
• Interior walls touch the outer boundary of the house only at the $N$ vertices.

For each test case, print one line in the form Case #x: C, where $x$ is the test case number starting from 1 and $C$ is the largest number of catnip flavors that the house can use. Print only this number; do not print the flavor assigned to each pillar.