Robot Commandos

Time Limit: 3 sec

 

The Problem

A group of robot commandos were assigned a critical task. They are assigned to defuse all bombs in a city. The city consists of several buildings and the buildings are connected by roads. A terrorist group place one bomb at the base of each building. The robot commandos must visit each building and defuse a bomb at the base of each building. They start their mission at the base of a particular building and from there they disseminate to reach each building. The robot commandos must use the available roads to travel between buildings. Any of them can visit one building after another, but they must all gather at a common place when their task in done.

 

In this problem, you will be given the description of different cities. Your job is to determine the minimum time needed to complete the mission. Each robot commando takes exactly one unit

of time to move between buildings. You may assume that the time required to defuse a bomb is negligible. Each robot commando can defuse unlimited number of bombs and there is an unlimited supply of robot commando for the mission.

 

The Input

The first line of input contains a number T < 100, where T denotes the number of test cases. Each case describes one city scenario. The first line of each case starts with a positive integer N <= 100, where N denotes the number of buildings in the city. The next line contains a positive integer R <= 1000, where R is the number of roads connecting two buildings. Each of the next R lines contain two distinct numbers, 0 <= u,v < N, this means there is a road connecting building u to building v. The buildings are numbered from 0 to N − 1. The last line of each case contains two integers 0 <= s, d < N. Where s denotes the building from where the mission starts and d denotes the building where they must meet.

 

The Output

For each case of input, there will be one line of output. It will contain the case number followed by the minimum time required to complete the mission.

 

Sample Input

1

4

3

0 1

1 2

2 3

0 3

 

Sample Output

Case 1: 3

 

 

 

Inter University Programming Contest - Summer 2019 [BGC Trust University Bangladesh]

Problem Setter: Shahin ShamS