Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem F: 六队-Walking

Problem F: 六队-Walking

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 84  Solved: 33
[Submit][Status][Web Board]

Description

​ Utopian来到了一个陌生的村庄。这个村子有n个路口,分别以编号1-n命名。该村的规划很有特点,任意一个路口必然与其它三个路口相通,即一个路口有三条不同方向的路。假设Utopian身处编号S的路口,他想要前往编号为E的路口,问假如他在每个路口都通过完全随机的方式选择道路,他能在k次随机选择之内到达目的地的概率是多少?

Input

多组数据,给出T为组数,保证

每组第一行给出四个整数n,S,E,k,保证

接着一个整数L,表示村中的道路数量。

之后L行,每行两个整数l,r,表示道路两端的路口编号。

Output

输出8位小数,表示选择内,能够到达目的地的概率。

Sample Input

1
8 3 8 1
12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 8
1 4
2 7
3 5
6 8

Sample Output

0.00000000

HINT

[Submit][Status][Web Board]