'
URI Online Judge | 1835

Campaign's Promise

Por Edson Alves, Faculdade UnB Gama BR Brazil

Timelimit: 3

In the electoral campaign, the mayor of the Barro Bravo made a promise: until the end of his mandate, the citizens would be able to travel between the city's main spots with no need of drive off-road (in the beginning of his term, this wasn't possible...).

The first resolution he took was to finish the partially build roads that had been started but not completed. At the end of these works, with a reduced budget, the mayor wished to know if the promise was accomplished or not, and if not, how many roads must still be constructed to honor his word.

Write a program that helps the mayor to find the desired information.

Input

The input consists in a series of test cases. The number T (T ≤ 100) of test cases is given in the first line of the input.

Each test case is composed by several lines. The first two lines contains, respectively, the values of N (1 ≤ N ≤ 100) and M (0 ≤ MN(N - 1)/2), where N is the number of main spots of the city and M is the number of roads completed by the mayor. The main spots are identified by a sequence of integer numbers that starts with number one.

The following M lines contains pairs of values X and Y (1 ≤ X, YN) that represents a road that connects the point X to the point Y.

Output

For each test case must be printed the message "Caso #t: ainda falta(m) E estrada(s)" or the message "Caso #t: a promessa foi cumprida" (if the promise was fulfilled), where t is the test case number and E is the minimum number of roads that must be constructed to honor the mayor promise.

Each message must be followed bye a newline character.

Input Samples Output Samples

4

3

2

1 3

2 3

4

2

1 2

3 4

3

0

6

5

1 2

1 3

1 4

2 3

3 4

Caso #1: a promessa foi cumprida

Caso #2: ainda falta(m) 1 estrada(s)

Caso #3: ainda falta(m) 2 estrada(s)

Caso #4: ainda falta(m) 2 estrada(s)