Inhaltsverzeichnis

Toll

Description

You are a truck driver that needs to deliver some cargo from one city to another. To accomplish this you are going to use the road network. A road connects exactly 2 cities. Not all cities are directly connected. For example if you want to get from the city A to the city B but the only roads that exist connect A with C and B with C then you will have to pass through the city C. Between 2 cities there is at most one road. Roads may always be used in both direction. Don't make any further assumptions about the topology of the road network. To pass a road you have to pay a tax of x€. All roads cost the same regardless of their length.

How much do you have to pay at least to complete your trip?

Input

The input begins with a single positive integer T on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Each test case starts with a line containing 5 positive integers: x, n, m, s and t.

After that the test case contains m lines each describing a road using its 2 end cities.

Output

The output should contain exactly T lines. The t-th line should contain the the amount you have to pay for the t-th testcase or -1 if you can't reach the city t. A line ends per definition with a newline character.

Sample Input

3

3 3 2 1 2
1 3
3 2

100 5 6 4 3
1 3
2 4
5 1
3 2
4 1
2 5

42 6 6 1 6
1 2
2 3
3 1
4 5
5 6
6 4

Sample Output

6
200
-1