A.I. War (작은 입력)

A.I. War는 Arcen Games가 만든 실시간 전략 게임이다. 이 문제는 그 게임에서 착안했지만, 게임을 해 본 적이 없어도 풀 수 있다.

당신은 은하의 미래를 걸고 인공지능과 싸우고 있다. 인공지능을 무너뜨리려면 인공지능의 본거지 행성을 위협해야 한다. 일부 행성은 웜홀로 이어져 있고, 한 행성이 웜홀로 이어지는 행성 수에는 제한이 없다.

처음에는 자신의 본거지 행성 하나만 소유한다. 매 턴마다 위협하고 있는 행성 중 하나를 정복할 수 있다. 어떤 행성을 소유하지 않았고 그 행성이 자신이 소유한 행성 중 하나와 웜홀로 이어져 있으면, 그 행성을 위협한다. 정복한 행성은 그때부터 소유한다. 인공지능의 본거지 행성을 위협하는 순간 더 이상 어떤 행성도 정복할 수 없다.

전술 학교에서 인공지능에 관한 두 가지 사실을 알아냈다.

• 행성을 하나 정복할 때마다 인공지능은 당신을 위협으로 판단해 방어 함선을 더 만들고, 그만큼 강해진다.
• 인공지능은 당신이 지금 위협하고 있는 모든 행성을 방어한다.

이 두 사실에서 다음 전략이 나온다.

1. 인공지능의 본거지 행성을 위협할 때까지 행성을 정복한다.
2. 1번을 만족하는 방법이 여러 가지면, 정복하는 행성 수가 가장 적은 방법을 쓴다.
3. 2번을 만족하는 방법이 여러 가지면, 마지막에 위협하는 행성 수가 가장 많은 방법을 쓴다.

행성과 웜홀이 주어질 때, 이 전략을 따르면 행성을 몇 개 정복하고 마지막에 몇 개를 위협하는지 구하라.

첫째 줄에 테스트 케이스 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 행성 수 $P$와 웜홀 수 $W$가 공백으로 구분되어 주어진다. 당신의 본거지 행성은 0번이고, 인공지능의 본거지 행성은 1번이다.

각 테스트 케이스의 둘째 줄에는 쉼표로 이어 붙인 정수 쌍 $x_i,y_i$가 $W$개, 공백으로 구분되어 주어진다. 각 쌍은 행성 $x_i$와 행성 $y_i$를 잇는 양방향 웜홀 하나를 뜻한다.

제한

• $1 \le T \le 50$
• $2 \le P \le 36$
• $1 \le W \le 630$
• $0 \le x_i < y_i < P$
• 같은 웜홀은 두 번 주어지지 않는다. 즉 $i \ne j$이면 $(x_i, y_i) \ne (x_j, y_j)$이다.
• 웜홀을 따라 0번 행성에서 1번 행성으로 가는 방법이 적어도 하나 있다.

각 테스트 케이스마다 Case #x: c t 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호, $c$는 이 전략을 따랐을 때 정복하는 행성 수, $t$는 마지막에 위협하는 행성 수다. $t$는 인공지능의 본거지 행성도 센다.

예제 입력에는 네 개의 경우가 들어 있다.

첫째 경우는 행성이 2개이고 웜홀 하나가 0번과 1번을 잇는다. 아무 행성도 정복하지 않아도 이미 인공지능의 본거지를 위협한다.

셋째 경우는 행성 하나만 정복하면 인공지능의 본거지를 위협한다. 마지막에 위협하는 행성은 2개이고, 어느 웜홀에도 이어지지 않은 행성이 하나 남는다.

넷째 경우는 4번 행성과 5번 행성을 정복하면 인공지능의 본거지를 위협한다. 마지막에 위협하는 행성은 6번, 2번, 3번, 그리고 인공지능의 본거지인 1번이다.