10177: LightOJ - Commandos
[Creator : ]
Description
A group of commandos were assigned a critical task. They are to destroy an enemy headquarter. The enemy head quarter consists of several buildings and the buildings are connected by roads.
The commandos must visit each building and place 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 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 enemy headquarters. Your job is to determine the minimum time needed to complete the mission.
Each commando takes exactly one unit of time to move between buildings.
You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.
The commandos must visit each building and place 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 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 desc
Each commando takes exactly one unit of time to move between buildings.
You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.
一群突击队员被指派执行一项重要任务。他们要摧毁敌人的一个总部。敌人的总部由几栋建筑组成，建筑之间有道路相连。 突击队员必须走访每座建筑，并在每座建筑的底部放置一枚炸弹。他们从某栋建筑的基座开始执行任务，然后分散到达每栋建筑。 突击队员必须使用可用的道路在建筑物之间穿行。他们中的任何一个人都可以一个接一个地访问一座大楼，但当他们的任务完成后，他们必须在一个共同的地点集合。 在这个问题中，您将得到不同敌人总部的描述。您的任务是确定完成任务所需的最短时间。 每个突击队员在建筑物之间移动正好需要一个单位的时间。 您可以假设放置炸弹所需的时间可以忽略不计。每个突击队员可携带的炸弹数量不受限制，任务中突击队员的数量也不受限制。
Input
Input starts with an integer $T\ (≤50)$, denoting the number of test cases.
The first line of each case starts with a positive integer $N\ (1 ≤ N ≤ 100)$, where $N$ denotes the number of buildings in the headquarter.
The next line contains a positive integer $R$, where $R$ is the number of roads connecting two buildings.
Each of the next $R$ lines contain two distinct numbers $u, v\ (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 $s, d\ (0 ≤ s, d < N)$. Where $s$ denotes the building from where the mission starts and $d$ denotes the building where they must meet.
You may assume that two buildings will be directly connected by at most one road. The input will be given such that, it will be possible to go from any building to another by using one or more roads.
The first line of each case starts with a positive integer $N\ (1 ≤ N ≤ 100)$, where $N$ denotes the number of buildings in the headquarter.
The next line contains a positive integer $R$, where $R$ is the number of roads connecting two buildings.
Each of the next $R$ lines contain two distinct numbers $u, v\ (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 $s, d\ (0 ≤ s, d < N)$. Where $s$ denotes the building from where the mission starts and $d$ denotes the building where they must meet.
You may assume that two buildings will be directly connected by at most one road. The input will be given such that, it will be possible to go from any building to another by using one or more roads.
Output
For each case, print the case number and the minimum time required to complete the mission.
Sample 1 Input
2
4
3
0 1
2 1
1 3
0 3
2
1
0 1
1 0
Sample 1 Output
Case 1: 4
Case 2: 1