Introduction

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.

Problem

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.:

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?

Input

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.

Output

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).

Limits

1 ≤ T ≤ 50.

0 ≤ x_i < y_i < P.

Each wormhole is unique: If i ≠ j, then (x_i, y_i) ≠ (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.

Memory limit: 1GB.

Small dataset (Test set 1 - Visible; 10 Points)

2 ≤ P ≤ 36.

1 ≤ W ≤ 630.

Time limit: 30 4 seconds.

Large dataset (Test set 2 - Hidden; 22 Points)

2 ≤ P ≤ 400.

1 ≤ W ≤ 2000.

Time limit: 60 8 seconds.

Sample

4
2 1
0,1
3 3
0,1 1,2 0,2
5 5
0,4 0,2 2,4 1,2 1,4
7 9
0,6 0,2 0,4 2,4 3,4 2,3 3,5 4,5 1,5

Case #1: 0 1
Case #2: 0 2
Case #3: 1 2
Case #4: 2 4

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).

Note

Arcen Games is the creator of A.I. War. Arcen Games does not endorse and has no involvement with Google Code Jam.