시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB108777.778%

문제

There are $n$ stations and $m$ directed roads between them.

One day, Chiaki is going from the $s$-th station to the $t$-th station, then back to the $s$-th station. Doing so, he needs to buy tickets for stations he passes. The price the tickets for the $i$-th station is $p_i$. If Chiaki buys a ticket for the $i$-th station, he can passes the station as many times as he wants. Find the minimum price of tickets to buy.

입력

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \leq T \leq 200$) indicating the number of test cases. For each test case:

The first line of each test case contains four integers $n$, $m$, $s$ and $t$ ($1 \leq n \leq 200$, $0 \leq m \leq n \times (n - 1)$, $1 \leq s, t \leq n$). The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \leq p_i \leq 100$). The $i$-th of the following $m$ lines contains two integers $a_i$ and $b_i$, which denote a road from the $a_i$ station to the $b_i$-th station ($1 \leq a_i, b_i \leq n$).

The sum of all $n$ does not exceed $200$.

출력

For each test case, output an integer denoting the answer. Print $-1$ for no solution.

예제 입력 1

3
4 5 1 4
1 1 1 1
1 2
2 3
3 1
4 2
3 4
4 4 1 2
1 1 1 1
1 2
2 3
3 4
4 1
4 8 1 3
1 100 1 1
1 2
2 1
2 3
3 2
1 4
4 1
3 4
4 3

예제 출력 1

4
4
3