该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

商品交易1trade.cpp
【问题描述】
市场上共有 N 种商品 ，编号从0到N-1 ，其中，第 i 种商品价值 Vi 元。
现在共有 M 个商人 ，编号从0到 M - 1 。在第j个商人这，你可以使用第xj 种商品交换第 yj 种商品。每个商人都会按照商品价值进行交易，具体来说，如果Vxj > Vyj ，他将会付给你 Vyj - Vxj 元钱 ；否则，那么你需要付给商人Vxj-Vyj 元钱。除此之外，每次交易商人还会收取 1 元作为手续费，不论交易商品的价值孰高孰低。
你现在拥有商品 a ，并希望通过一些交换来获得商品 b 。请问你至少要花费多少钱？
（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱 。）
【输入描述】
第一行四个整数N, M, a, b，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证 0 ≤ a, b ＜N ，保证 a ≠ b 。
第二行N 个用单个空格隔开的正整数 V0，V1，……，VN-1 ，依次表示每种商品的价值 。保证 1 ≤ Vi ≤ 10的9次方 。
接下来 M 行 ，每行两个整数 Xj, Yj，表示第j 个商人愿意使用第 Xj 种商品交换第 Yj 种商品。保证0≤Xj, Yj ＜ N， 保证 Xj≠Yj 。
【输出描述】
输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品b，请输出“No solution”
【样例输入 1】
3 5 0 2
1 2 4
1 0
2 0
0 1
2 1
1 2
【样例输出 1】
5
【样例解释 1】
可以先找 2 号商人，花 2 - 1 = 1 元的差价以及 1 元手续费换得商品 1 ，再找 4 号商人，花 4 - 2 = 2 元的差价以及1元手续费换得商品 2 。总计花费 1 + 1 + 2 + 1 = 5 元。
【样例输入 2】
3 3 0 2
100 2 4
0 1
1 2
0 2
【样例输出 2】
-95
【样例解释 2】
可以找 2 号商人 ，直接换得商品 2 的同时 ，赚取 100-4 = 96 元差价 ，再支付 1 元手续费，净赚 95 元。
也可以先找0号商人换取商品 1 ，再找1号商人换取商品 2 ，不过这样只能赚 94元。
【样例输入 3】
4 4 3 0
1 2 3 4
1 0
0 1
3 2
2 3
【样例输出 3】
No solution
【数据规模】
对于30%的测试点 ，保证N ≤ 10 ，M ≤ 20 。
对于70%的测试点 ，保证N ≤ 1000， M ≤ 10000。
对于100%的测试点 ，保证 N ≤ 100000 ，M ≤ 200000