问题描述

市场上共有N种商品，编号从0至N-1，第i种商品价值$v_i$元。 共有M个商人，编号从0至M-1，第j个商人支持你使用第$x_j$种商品交换第$y_j$种商品，交易规则如下：

• 若$v_{xj} > v{yj}$，商人会付给你$v{xj} - v{y_j}$元；
• 若$v_{xj} \leq v{yj}$，你需要付给商人$v{yj} - v{x_j}$元；
• 每次交易无论盈亏，都需要额外支付1元手续费。 你当前持有商品a，希望通过若干次交换获得商品b，请求出完成目标的最小花费（花费可为负数，表示交易过程中盈利）。

输入描述

1. 第一行四个整数N、M、a、b，分别表示商品数量、商人数量、初始持有商品编号、目标商品编号，满足$0 \leq a < N$，$a \neq b$。
2. 第二行N个用空格分隔的正整数$v_0, v1, ..., v{N-1}$，表示每种商品的价值，满足$1 \leq v_i \leq 10^9$。
3. 接下来M行，每行两个整数$x_j、y_j$，表示第j个商人支持用$x_j$交换$y_j$，满足$0 \leq x_j, y_j < N$，$x_j \neq y_j$。

输出描述

输出一行一个整数，表示最小花费；若无法通过交换得到商品b，输出No solution。 注意：输入输出不要附带任何额外提示信息。

样例说明

样例输入1

3 5 0 2
1 2 4
1 2
1 0
2 0
0 1
1 2

样例输出1

5

样例解释1

最优路径为0→1→2：

• 0换1：补差价2-1=1元，加1元手续费，共花费2元；
• 1换2：补差价4-2=2元，加1元手续费，共花费3元； 总花费2+3=5元。

样例输入2

3 3 0 2
100 2 4
0 1
1 2
0 2

样例输出2

-95

样例解释2

最优路径为0→2：

• 0换2：商人退差价100-4=96元，扣除1元手续费，净赚95元，即花费-95元。

样例输入3

4 4 3 0
1 2 3 4
1 0
0 1
3 2
2 3

样例输出3

No solution

样例解释3

商品3所在的连通分量与商品0所在的连通分量不连通，无法完成交换。

数据规模

• 30%的测试点：$N \leq 10, M \leq 20$
• 70%的测试点：$N \leq 10^3, M \leq 10^4$
• 100%的测试点：$N \leq 10^5, M \leq 2 \times 10^5$