A.I. War (Large)

A.I. War는 Arcen Games가 개발한 실시간 전략 게임이다. 이 문제는 그 게임에서 아이디어를 얻었지만, 게임을 해 본 적이 없어도 풀 수 있다.

은하의 미래가 걸린 전쟁에서 인공지능과 맞서고 있다. 인공지능을 무너뜨리려면 인공지능의 본거지 행성을 위협해야 한다. 어떤 행성 쌍은 웜홀로 이어져 있고, 한 행성은 웜홀로 몇 개의 행성과도 이어질 수 있다.

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

전술학교의 가장 중요한 수업에서 인공지능에 관해 두 가지를 알아냈다.

• 행성을 하나 정복할 때마다 인공지능은 더 강해진다. 자신을 위협으로 여기고 방어 함선을 더 만들기 때문이다.
• 인공지능은 현재 위협받는 행성을 모두 방어한다.

이 두 사실을 묶어 다음 전략을 세웠다.

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

행성과 웜홀이 주어진다. 이 전략을 따라 인공지능의 본거지에 이르렀을 때 정복한 행성은 몇 개이고, 위협하는 행성은 몇 개인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 행성의 수 $P$와 웜홀의 수 $W$가 공백을 사이에 두고 주어진다. 자신의 본거지 행성은 0번, 인공지능의 본거지 행성은 1번이다.

각 테스트 케이스의 둘째 줄에는 $x_i$,$y_i$ 꼴의 쌍이 $W$개 공백을 사이에 두고 주어진다. 각 쌍은 행성 $x_i$와 행성 $y_i$를 잇는 양방향 웜홀이 있다는 뜻이다.

제한

• $1 \le T \le 50$
• $2 \le P \le 400$
• $1 \le W \le 2000$
• $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$에는 인공지능의 본거지 행성도 포함된다.

첫 번째 예제의 첫 번째 케이스에서는 아무것도 정복하지 않아도 이미 인공지능의 본거지를 위협한다.

첫 번째 예제의 세 번째 케이스에서는 행성 하나만 정복하면 인공지능의 본거지를 위협한다. 마지막에 위협하는 행성은 두 개이고, 어느 행성과도 이어지지 않은 행성이 하나 남는다.

첫 번째 예제의 네 번째 케이스에서는 행성 4와 행성 5를 정복하면 인공지능의 본거지를 위협한다. 마지막에 위협하는 행성은 6, 2, 3, 1이고, 이 중 1이 인공지능의 본거지다.

Arcen Games는 A.I. War를 만든 회사이며, 이 문제와는 관련이 없다.