Fegla의 스쿠터 시험 주행

Fegla는 건물 안에서 작은 스쿠터를 타고 다닌다. 대회 심사를 맡고 있던 날 스쿠터가 고장 났고, Hamzawy가 심사실에서 고쳐 주었다. Fegla는 수리가 제대로 됐는지 확인하려고 심사실을 나가 건물을 한 바퀴 돈 뒤 출발한 방으로 돌아오려 한다. 심사진을 오래 비워 둘 수 없으니 지나는 방의 수가 가장 적은 경로를 고르려 하는데, 출발한 방 말고 다른 방을 적어도 하나는 지나야 한다.

Fegla는 문을 열지 못하고 스쿠터로 밀기만 하므로 두 방을 잇는 연결은 정해진 한 방향으로만 통과할 수 있다.

방의 개수와 방 사이의 연결이 주어진다. 어떤 방에서 출발해 다른 방을 하나 이상 지난 뒤 같은 방으로 돌아오는 순환 경로 가운데, 지나는 서로 다른 방의 개수가 가장 적은 값을 구하라. 예를 들어 방 $1$에서 방 $2$, 방 $3$을 거쳐 방 $1$로 돌아오는 경로가 지나는 방은 $3$개다. 조건상 답은 항상 $2$ 이상이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스의 첫 줄에는 방의 개수 $N$과 연결의 개수 $M$이 공백으로 구분되어 주어진다 ($1 \le N \le 1000$, $0 \le M \le 10^6$).

이어지는 $M$개의 줄에는 서로 다른 두 정수 $u$와 $v$가 공백으로 구분되어 주어진다 ($1 \le u, v \le N$). 방 $u$에서 방 $v$로 가는 연결이 있다는 뜻이다. 같은 두 방 사이에 연결이 여러 개 있을 수 있고, 두 방을 잇는 경로도 여러 개일 수 있다.

각 테스트 케이스마다 한 줄에 Case n: R 형식으로 출력한다. $n$은 $1$부터 시작하는 테스트 케이스 번호이고, $R$은 조건을 만족하는 가장 짧은 순환 경로가 지나는 서로 다른 방의 개수다. 그런 경로가 없으면 $R$은 $-1$이다.