A.I. War (Large)

A.I. War is a real time strategy game developed by Arcen Games. This problem takes its idea from that game, but you do not need to have played it.

You are fighting an artificial intelligence in a war that decides the future of the galaxy. To bring the A.I. down you have to threaten its home planet. Some pairs of planets are connected by wormholes, and one planet may be connected to any number of other planets.

At the start you own only your own home planet. Each turn you may conquer one planet that you threaten. You threaten a planet if you do not own it and it is connected by a wormhole to one of the planets you own. A planet you conquer is yours from that moment on. Once you threaten the A.I.'s home planet, you may not conquer any more planets.

During the most important lesson in tactical school you learned two things about the A.I.

• Every planet you conquer makes the A.I. stronger, because it sees you as a threat and builds more ships to defend itself.
• The A.I. defends every planet you are currently threatening.

You combined those two facts into a strategy.

1. Conquer planets until you threaten the A.I.'s home planet.
2. If several ways finish step 1, take the one that conquers the smallest number of planets.
3. If several ways satisfy step 2, take the one that threatens the largest number of planets at the end.

You are given the planets and the wormholes. Following this strategy, how many planets do you conquer on the way to the A.I.'s home planet, and how many planets do you threaten at the end?

The first line contains the number of test cases $T$. The first line of each test case contains the number of planets $P$ and the number of wormholes $W$, separated by a space. Your home planet is planet 0 and the A.I.'s home planet is planet 1.

The second line of each test case contains $W$ pairs of the form $x_i$,$y_i$, separated by spaces. Each pair means that a two way wormhole connects planet $x_i$ and planet $y_i$.

Limits

• $1 \le T \le 50$
• $2 \le P \le 400$
• $1 \le W \le 2000$
• $0 \le x_i < y_i < P$
• All wormholes are distinct: if $i \ne j$, then $(x_i, y_i) \ne (x_j, y_j)$.
• There is at least one way to reach planet 1 from planet 0 through wormholes.

For each test case, print one line in the form Case #x: c t. Here $x$ is the test case number starting from 1, $c$ is the number of planets you conquer under the strategy, and $t$ is the number of planets you threaten at the end. The A.I.'s home planet counts toward $t$.

In the first case of the first example you threaten the A.I.'s home planet already, so you conquer nothing.

In the third case of the first example one conquest is enough to threaten the A.I.'s home planet. You end up threatening two planets, and one planet is left that is connected to nothing.

In the fourth case of the first example you threaten the A.I.'s home planet after conquering planets 4 and 5. At the end you threaten planets 6, 2, 3 and 1, and planet 1 is the A.I.'s home planet.

Arcen Games is the company that made A.I. War, and it has no connection with this problem.