A.I. 전쟁

은하계의 미래를 건 치명적인 전쟁에서 인공지능과 맞서고 있다. A.I.를 물리치려면 그 모행성을 위협해야 한다. 일부 행성은 웜홀로 서로 연결되어 있으며, 어떤 행성이든 웜홀을 통해 임의의 개수의 다른 행성과 연결될 수 있다.

처음에는 자신의 모행성만 소유한다. 매 턴 위협하고 있는 어떤 행성이든 정복할 수 있다. 자신이 소유하지 않은 행성이 자신이 소유한 행성 중 어느 하나와 웜홀로 연결되어 있으면 그 행성을 위협한다. 행성을 정복하고 나면 그 행성을 소유한다. A.I.의 모행성을 위협하게 되는 즉시 더 이상 행성을 정복할 수 없다.

전술 학교에서 가장 중요한 날의 수업을 듣던 중, A.I.에 관한 두 가지 사실을 알아냈다.

• 행성을 하나 정복할 때마다 A.I.는 당신을 위협으로 간주하고 스스로를 방어할 함선을 더 많이 생산하므로 더 강력해진다.

• A.I.는 당신이 현재 위협하고 있는 모든 행성을 방어한다.

이 두 사실을 결합하여 다음 전략을 세웠다.

• A.I.의 본거지를 위협할 때까지 행성을 정복한다.

• 단계 1을 완료하는 방법이 여러 가지라면, 가능한 한 가장 적은 수의 행성을 정복하는 방법을 택한다.

• 단계 2을 완료하는 방법이 여러 가지라면, 마지막에 가능한 한 가장 많은 수의 행성을 위협하게 되는 방법을 택한다.

행성과 웜홀이 주어질 때, 위에서 설명한 전략을 따르면 A.I.의 본거지로 가는 도중에 몇 개의 행성을 정복하고 위협하게 되는가?

제한

1 ≤ T ≤ 50. 0 ≤ $x_{i}$ < $y_{i}$ < P. 각 웜홀은 고유하다. 즉, i ≠ j이면 ($x_{i}$, $y_{i}$) ≠ ($x_{j}$, $y_{j}$)이다. 일련의 웜홀을 이용하여 자신의 모행성에서 A.I.의 모행성에 도달하는 방법이 적어도 하나 존재한다. 메모리 제한: 1GB.

작은 데이터 세트(테스트 세트 1 - 공개)

2 ≤ P ≤ 36. 1 ≤ W ≤ 630. 시간 제한: 30초.

큰 데이터 세트(테스트 세트 2 - 비공개)

2 ≤ P ≤ 400. 1 ≤ W ≤ 2000. 시간 제한: 60초.

입력의 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 P와 W가 있는 한 줄로 시작하며, P는 행성의 수이고 W는 웜홀의 수이다. 자신의 모행성은 행성 0이고, A.I.의 모행성은 행성 1이다.

각 테스트 케이스의 두 번째 줄에는 공백으로 구분된 W개의 정수 쌍 $x_{i}$,$y_{i}$가 주어지며, 각 쌍의 정수는 쉼표로 구분된다. 각 쌍은 행성 $x_{i}$과 $y_{i}$을 연결하는 양방향 웜홀이 있음을 나타낸다.

각 테스트 케이스마다 "Case #x: c t"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, c는 위 전략을 따를 때 정복하는 행성의 수이며, t는 마지막에 위협하는 행성의 수(A.I.의 모행성 포함)이다.

Arcen Games는 A.I. 전쟁의 제작자이다. Arcen Games는 Google Code Jam.를 지지하지 않으며 이에 관여하지도 않았다.

설명

첫 번째 케이스에서는 아무것도 정복할 필요가 없으며, 이미 A.I.의 모행성을 위협하고 있다.

세 번째 케이스에서는 행성을 하나만 정복한 뒤 A.I.의 모행성을 위협할 수 있다. 마지막에는 두 행성을 위협하며, 아무것과도 연결되지 않은 행성이 하나 더 있다.

네 번째 케이스에서는 행성 4과 5을 정복하여 A.I.의 모행성을 위협할 수 있다. 마지막에는 행성 6, 2, 3, 1(A.I.의 모행성)을 위협한다.