CCO Preparation Test 1 P2 - Escape Maze

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 0.6s
Memory limit: 128M
Author:
bruce
Problem type

Bruce is designing an escape maze game for his students. The maze can be treated as an undirected graph. Each vertex in the graph is a room, and there are hallways (edges) that connect two rooms together. Each room has at least one hallway connecting it to some other room. Some rooms in the maze are set as exits. Initially, students may start from any room, and they need to find a path to any exit to escape the maze. But Bruce doesn't want the game to be too easy. So, he decides to close one room during the game. However, Bruce has to ensure that, no matter which room is closed, there always exists a path to one exit for any student in the maze. Please write a program to help Bruce to decide the least number of required exits in the maze and the number of different ways to place the exits. Two ways of placing exits are different if any room is an exit in the one way but it isn't in the other way.

Note: Bruce can only close one room during the game, and the closed room may be an exit. Also, the graph may be initially disconnected.

Input Specification

The input includes multiple test cases, up to 3.

The first line of input will consist of an integer N (1 \le N \le 500), which is the number of hallways.

Each of the next N lines will consist of two integers S and T (1 \le S, T \le 400), which are two rooms connected by a hallway.

The input is terminated by a single 0.

Output Specification

For each test case in the input, output two integers on a single line. The first integer is the least number of required exits to make sure that, no matter which room is closed by Bruce, there is always a path to one exit for any student in the maze. The second integer is the number of different ways to design the maze with the least number of exits.

Both output numbers will be less than 2^{64}.

Sample Input

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

Sample Output

2 4
4 1

Explanation of Output for Sample Input

The least number of exits for case 1 is 2. There are 4 different ways to place the two exits: (2, 4), (3, 4), (4, 5), (4, 6).

The least number of exits for case 2 is 4. There is only 1 way to place the four exits: (4, 5, 6, 7).

Comments


  • 4
    kobortor  commented on June 11, 2015, 1:16 a.m.

    1) Multiple Hallways between the same rooms?

    2) Selfloops


    • 3
      bruce  commented on June 11, 2015, 10:03 p.m.

      1) there may be multiple hallways between rooms

      2) no selfloops. each hallway connected two rooms (not same room).


    • 3
      fifiman  commented on June 11, 2015, 3:49 a.m.

      Well neither is specified, so assume yes


  • -2
    TiedyeC  commented on March 1, 2015, 10:32 p.m.

    Is it just me or would (1, 4) be a valid exit placement for the first case?


    • 1
      root  commented on June 15, 2017, 11:16 p.m.

      Close room 1, and you can't reach an exit from room 2,3,5,6