A.I. War (Small)

A.I. War is a real-time strategy game made by Arcen Games. This problem was inspired by that game, but you do not need to have played it.

You are fighting an artificial intelligence for the future of the galaxy. To defeat the A.I. you have to threaten its home planet. Some planets are connected to each other by wormholes, and a planet may be connected to any number of other planets.

You start out owning only your own home planet. Each turn you may conquer any planet 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. Once you conquer a planet, you own it. As soon as you threaten the A.I.'s home planet, you may not conquer any more planets.

At tactical school you learned two facts about the A.I.

• Every planet you conquer makes the A.I. stronger, because it treats you as a threat and builds more defending ships.
• The A.I. defends every planet you currently threaten.

Those two facts give you a strategy.

1. Conquer planets until you threaten the A.I.'s home planet.
2. If several ways complete step 1, use one that conquers the smallest number of planets.
3. If several ways complete step 2, use one that ends up threatening the largest number of planets.

Given the planets and the wormholes, find how many planets you conquer and how many you threaten at the end when you follow this strategy.

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains two space separated integers, the number of planets $P$ and the number of wormholes $W$. 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$ space separated pairs of comma separated integers $x_i,y_i$. Each pair means one two way wormhole connecting planet $x_i$ and planet $y_i$.

Limits

• $1 \le T \le 50$
• $2 \le P \le 36$
• $1 \le W \le 630$
• $0 \le x_i < y_i < P$
• No wormhole is given twice. That is, 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 along wormholes.

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

The sample input holds four cases.

In the first case there are 2 planets and one wormhole joins planet 0 and planet 1. You conquer nothing and already threaten the A.I.'s home planet.

In the third case one conquest is enough to threaten the A.I.'s home planet. You end up threatening 2 planets, and one planet is left that no wormhole touches.

In the fourth case you threaten the A.I.'s home planet after conquering planets 4 and 5. You end up threatening planets 6, 2, 3, and planet 1, the A.I.'s home planet.