P13377 [GCJ 2011 #2] A.I. War

A.I. War is a real-time strategy game developed by Arcen Games. This problem was inspired by the game, but does not assume you have played it. Arcen Games is the creator of A.I. War. Arcen Games does not endorse and has no involvement with Google Code Jam.

You're facing an artificial intelligence in a deadly war for the future of the galaxy. In order to defeat the A.I., you will need to threaten its $home\ planet$. Some planets are connected to each other by wormholes; any planet may be connected to any number of other planets using the wormholes. You begin by owning only your home planet. Each turn, you may conquer any planet you $threaten$. You threaten a planet if you don't own it, and it is connected by a wormhole to any of the planets you own. Once you have conquered a planet, you own it. As soon as you threaten the A.I.'s home planet, you may not conquer any more planets. While attending the most important day in tactical school, you discovered two things about the A.I.: * For each planet you conquer, the A.I. will become more powerful, because it will see you as a threat and produce more ships to defend itself. * The A.I. will defend every planet you're currently threatening. You have combined those two facts to create a strategy: 1. You will conquer planets until you threaten the A.I.'s home base. 2. If there are multiple ways of completing step 1, do it while conquering the $smallest$ possible number of planets. 3. If there are multiple ways of completing step 2, do it so that at the end you will threaten the $largest$ possible number of planets. Given the planets and the wormholes, how many planets will you conquer and threaten on your way to the A.I.'s home base if you follow the strategy described above?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a single line containing two space-separated integers: $P$, the number of planets, and $W$, the number of wormholes. Your home planet is planet $0$, and the A.I.'s home planet is planet $1$. The second line of each test case will contain $W$ space-separated pairs of comma-separated integers $x_{i}, y_{i}$. Each of these indicates that there is a two-way wormhole connecting planets $x_{i}$ and $y_{i}$.

For each test case, output one line containing "Case #$x$: $c\ t$", where $x$ is the case number (starting from $1$), $c$ is the number of planets you conquer if you follow the above strategy, and $t$ is the number of planets you threaten at the end (including the A.I.'s home planet).

**Sample Explanation** In the first case, you don't have to conquer anything, and you're already threatening the A.I.'s home planet. In the third case, you can threaten the A.I.'s home planet after conquering only one planet. You end up threatening two planets, and there's an extra planet that isn't connected to anything. In the fourth case, you can threaten the A.I.'s home planet by conquering planets $4$ and $5$. You end up threatening planets $6$, $2$, $3$ and $1$ (the A.I.'s home planet). **Limits** - $1 \leq T \leq 50$. - $0 \leq x_{i} < y_{i} < P$. - Each wormhole is unique: If $i \neq j$, then $(x_{i}, y_{i}) \neq (x_{j}, y_{j})$. - There will be at least one way to reach the A.I.'s home planet from your home planet using a series of wormholes. **Small dataset (10 Pts, Test set 1 - Visible)** - $2 \leq P \leq 36$. - $1 \leq W \leq 630$. - Time limit: ~~30~~ 3 seconds. **Large dataset (22 Pts, Test set 2 - Hidden)** - $2 \leq P \leq 400$. - $1 \leq W \leq 2000$. - Time limit: ~~60~~ 6 seconds.