Description

有$N$ $（$$2$$≤$$N$ $≤$$1$$0$$0$$）$个城市，并且有$M$$（$$M$ $≤$$1$$0$$0$$0$$0$$）$条双向道路连接各个城市。一群窃贼计划盗窃$H$ 市的博物馆。警察知道了这个计划，计划抓住窃贼。窃贼目前在城市里，警察想在$S$ 到$H$ 的路上抓住他们。警察已经收集了$I$ 市需要逮捕的窃贼人数$（$$1$$≤$$I$ $≤$$N$ $）$。警察不想在$S$ 市或$H$ 市遇到窃贼，想抓最少的人完成任务。

Input

第$1$行包含测试用例的数量$T$ $（$$T$ $≤$$1$$0$$）$。每个测试用例的第$1$行都有$4$个整数：城市数量$N$ ；道路数量$M$ ；城市标签$S$ $（$$1$$≤$$S$ $≤$$N$$）$；城市标签$H$ $（$$1$$≤$$H$ $≤$$N$ ，$S$ ≠$H$ $）$。第$2$行包含$N$ 个整数，表示每个城市需要逮捕的窃贼人数，这$N$ 个整数之和小于$1$$0$$0$$0$$0$。接着是$M$行，每行都包含两个整数$x$ 和$y$ ，表示在$x$ 和$y$ 之间有一条双向道路。注意：在$S$ 和$H$ 之间没有道路。在每个测试用例后面都有一个空行。

Output

对每个测试用例，都单行输出警察需要抓到的最少窃贼人数。

Samples

1
5 5 1 5
1 6 6 11 1
1 2
1 3
2 4
3 4
4 5

11