Fegla's Scooter Test Ride

Fegla rides a small scooter to get around inside a building. On the day he was judging a contest his scooter broke down, and Hamzawy repaired it in the judging room. To check that the repair worked, Fegla wants to leave the judging room, ride a loop through the building, and come back to the room he started from. He cannot leave the judging team alone for long, so he wants the route that passes through the fewest rooms, and the route has to visit at least one room other than the starting one.

Fegla cannot open doors, he can only push them with the scooter, so a connection between two rooms can be taken in one fixed direction only.

You are given the number of rooms and the connections between them. Find the smallest number of distinct rooms on a route that starts at some room, visits at least one other room, and returns to the starting room. For example, a route that goes from room $1$ to room $2$, then to room $3$, then back to room $1$ passes through $3$ rooms. The answer is therefore always at least $2$.

The first line contains one integer $T$, the number of test cases ($1 \le T \le 100$).

The first line of each test case contains two integers $N$ and $M$ separated by a space, the number of rooms and the number of connections ($1 \le N \le 1000$, $0 \le M \le 10^6$).

Each of the next $M$ lines contains two different integers $u$ and $v$ separated by a space ($1 \le u, v \le N$), meaning there is a connection that goes from room $u$ to room $v$. A pair of rooms may have several connections and several routes between them.

For each test case print one line in the form Case n: R, where $n$ is the test case number starting from $1$ and $R$ is the number of distinct rooms on the shortest such route. If no such route exists, $R$ is $-1$.