KRH Is A God
Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 221 Accepted Submission(s) : 37
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
As we all know, KRH lives in SCNU as a god. We always meet him in dining hall, or in training room, or in college building, or in front of the dormitory, even on a side road. Evil smile is always shown on his face. That\'s terrible, so a retired ACMer, LiJunLe decides to track him.
LiJunLe finds that, KRH starts strolling from the dining hall every time. When he runs out of his power, he will stop here and not go any more. That is, the distance he walks pass relates with how many calories KRH gets in dinner.
Today, LiJunLe stays in his dormitory, West 2. As you know, the dormitory West 2 is older than most of students in SCNU. That is a legend! It is founded in 1986, so far to stand for more than 20 years. Besides friendly mice, crouching tigers and hidden dragon are also living in West 2 dormitory. Seen from the photo below, The dormitory locates at good position, provides reasonable layout, has well equipments and uses advanced management solution. The dormitory is only for our South China Normal School students. It is a real ideal place for living and studying!
But now, LiJunLe is bored, and think whether KRH will stop at West 2 or not. He wants to know what is the probability?
To simplify the problem, suppose the map of SCNU is an undirected graph. Suppose each building as a node, and the distance between two building is one unit of length. If KRH gets one unit of calories, he can walk exactly one unit of length. By the way, KRH will not hang around the street.
When KRH reaches a building, he will choose any one road randomly. It means that the probability of selecting any road is absolutely equal.
There are n buildings in SCNU. The node index of the dining hall is always 1, and West 2 dormitory is always 2.
LiJunLe finds that, KRH starts strolling from the dining hall every time. When he runs out of his power, he will stop here and not go any more. That is, the distance he walks pass relates with how many calories KRH gets in dinner.
Today, LiJunLe stays in his dormitory, West 2. As you know, the dormitory West 2 is older than most of students in SCNU. That is a legend! It is founded in 1986, so far to stand for more than 20 years. Besides friendly mice, crouching tigers and hidden dragon are also living in West 2 dormitory. Seen from the photo below, The dormitory locates at good position, provides reasonable layout, has well equipments and uses advanced management solution. The dormitory is only for our South China Normal School students. It is a real ideal place for living and studying!
But now, LiJunLe is bored, and think whether KRH will stop at West 2 or not. He wants to know what is the probability?
To simplify the problem, suppose the map of SCNU is an undirected graph. Suppose each building as a node, and the distance between two building is one unit of length. If KRH gets one unit of calories, he can walk exactly one unit of length. By the way, KRH will not hang around the street.
When KRH reaches a building, he will choose any one road randomly. It means that the probability of selecting any road is absolutely equal.
There are n buildings in SCNU. The node index of the dining hall is always 1, and West 2 dormitory is always 2.
Input
The first line is a number T (1<=T<=30), indicating the number of test cases below.
In each test case, two numbers, n (2<=n<=200), m (1<=m<=30000) and k (1<=k<=50000) are displayed. The number n indicates the number of buildings in SCNU, m indicates the number of roads in SCNU, and k indicates the calories KRH gets before strolling.
Then, m lines follow. Each line contains two numbers, a and b (1<=a,b<=n, a!=b), indicates building with number a and b are connected by a road.
In each test case, two numbers, n (2<=n<=200), m (1<=m<=30000) and k (1<=k<=50000) are displayed. The number n indicates the number of buildings in SCNU, m indicates the number of roads in SCNU, and k indicates the calories KRH gets before strolling.
Then, m lines follow. Each line contains two numbers, a and b (1<=a,b<=n, a!=b), indicates building with number a and b are connected by a road.
Output
One line for one test case, containing "Case #D: E". "D" is the index of the test case, starting from 1, and "E" is the probability LiJunLe wants, corrects to 0.0001.
Sample Input
3 2 1 1 1 2 3 2 2 3 1 2 3 3 1 5 1 3
Sample Output
Case #1: 1.0000 Case #2: 0.5000 Case #3: 0.0000
Source
华南师范大学·2012年ACM程序设计竞赛·决赛