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?

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.

• x is tax amount you have to pay per road (1≤x≤1000)
• n is the number of cities. The cities are number from 1 to n. (1≤n≤10000)
• m is the number of roads. (1≤m≤10000)
• s is the city you start in. (1≤s≤n)
• t is the city you want to get to. (1≤t≤n)

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

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.

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

6
200
-1