H - Hurry Chinchilla!

Languages: C, C++, Java, Python, Kotlin
Time & Memory limits: (details)
 
<div style="text-align: justify">
It's been a few years since researchers began studying a theoretical device called a chinchilla router.
When the router receives a packet that is not destined for a computer in its local network, the device randomly chooses one of the other routers connected to it with equal probability and forwards the packet to that router. This process continues until the packet arrives at its intended destination. The routers don't track whether a packet has already passed through before, so a packet may pass through the same router repeatedly on its way to its destination. The device was proposed by a graduate student from the Republic of Incadelia who imagined passing messages by training chinchillas to navigate a series of tubes.
We would like to take a closer look at this model. We say a packet made an *antioptimal* hop if it gets sent to a router without getting closer to the destination. Your task is to create a program that receives a description of a network of chinchilla routers and finds the expected number of antioptimal hops that would occur when sending a packet.
</div>

It's been a few years since researchers began studying a theoretical device called a chinchilla router.

When the router receives a packet that is not destined for a computer in its local network, the device randomly chooses one of the other routers connected to it with equal probability and forwards the packet to that router. This process continues until the packet arrives at its intended destination. The routers don't track whether a packet has already passed through before, so a packet may pass through the same router repeatedly on its way to its destination. The device was proposed by a graduate student from the Republic of Incadelia who imagined passing messages by training chinchillas to navigate a series of tubes.

We would like to take a closer look at this model. We say a packet made an antioptimal hop if it gets sent to a router without getting closer to the destination. Your task is to create a program that receives a description of a network of chinchilla routers and finds the expected number of antioptimal hops that would occur when sending a packet.

Input

 
<div style="text-align: justify">
The input will begin with a single line containing an integer $T$, where $1 \le T \le 100$. Then $T$ test cases will follow.
Each test case will begin with a line consisting of three integers $N$, $G$, and $K$, separated by single spaces. $N$ will be the number of chinchilla routers in the network, where $2 \le N \le 10$. The routers will be numbered $1$ through $N$. The starting router will always be number $1$ and the destination router will be indicated by $G$, where $G \ge 2$. $K$ will be the number of connections in the network, where $0 \le K < N^2$.
The following $K$ lines will consist of two integers $U$ and $V$, where $U$ and $V$ will be integers in the range $[1, N]$. Each line will specify that a distinct bidirectional link exists between routers $U$ and $V$. Each pair will appear once at most (so if "1 2" appears in the input, then "2 1" will not). Routers will never be connected to themselves.
</div>

The input will begin with a single line containing an integer $T$, where $1 \le T \le 100$. Then $T$ test cases will follow.

Each test case will begin with a line consisting of three integers $N$, $G$, and $K$, separated by single spaces. $N$ will be the number of chinchilla routers in the network, where $2 \le N \le 10$. The routers will be numbered $1$ through $N$. The starting router will always be number $1$ and the destination router will be indicated by $G$, where $G \ge 2$. $K$ will be the number of connections in the network, where $0 \le K < N^2$.

The following $K$ lines will consist of two integers $U$ and $V$, where $U$ and $V$ will be integers in the range $[1, N]$. Each line will specify that a distinct bidirectional link exists between routers $U$ and $V$. Each pair will appear once at most (so if "1 2" appears in the input, then "2 1" will not). Routers will never be connected to themselves.

Output

 
<div style="text-align: justify">
For each test case, output a single line containing the expected number of antioptimal hops that would occur while transporting a packet from router $1$ to router $G$. The answer should be rounded to $3$ decimal places. If there is no route to the goal, then output "NO ROUTE". The order of the output must follow the order in which the test cases are provided.
<div/>


For each test case, output a single line containing the expected number of antioptimal hops that would occur while transporting a packet from router $1$ to router $G$. The answer should be rounded to $3$ decimal places. If there is no route to the goal, then output "NO ROUTE". The order of the output must follow the order in which the test cases are provided.

Sample test(s)

Input
4 3 2 1 1 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4 4 4 3 1 2 1 3 1 4 4 4 4 1 2 1 3 1 4 2 4
Output
NO ROUTE 2.000 2.000 1.667