Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1139.

Problem Description

There are $N$ types of commodities in the market, numbered from $0$ to $N-1$. The value of commodity $i$ is $v_i$ yuan.

There are $M$ merchants, numbered from $0$ to $M-1$. At merchant $j$, you can trade the commodity $x_j$ you have for the commodity $y_j$ the merchant has. Each merchant trades based on the commodity values. Specifically, if $v_{x_j} > v_{y_j}$, the merchant will pay you $(v_{x_j} - v_{y_j})$ yuan; otherwise, you need to pay the merchant $(v_{y_j} - v_{x_j})$ yuan. In addition, for each trade the merchant charges a fee of $1$ yuan, no matter which commodity is more valuable.

You currently have commodity $a$ and want to obtain commodity $b$ through some trades. What is the minimum amount of money you need to spend? (This minimum cost can be negative, meaning you can earn some money while achieving the goal.)

Input Format

The first line contains four integers $N, M, a, b$, representing the number of commodities, the number of merchants, the commodity you currently have, and the commodity you want to obtain. It is guaranteed that $0 \le a, b < N$, and $a \ne b$.

The second line contains $N$ positive integers $v_0, v_1, …, v_{N-1}$ separated by single spaces, representing the value of each commodity. It is guaranteed that $1 \le v_i \le 10^9$.

The next $M$ lines each contain two integers $x_j, y_j$, meaning that at merchant $j$, you can trade commodity $x_j$ for commodity $y_j$. It is guaranteed that $0 \le x_j, y_j < N$, and $x_j \ne y_j$.

Output Format

Output one integer on a single line, representing the minimum cost. In particular, if it is impossible to obtain commodity $b$ through trades, output No solution.

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

5

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

-95

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

No solution

Hint

Constraints

For $30\%$ of the testdata, $N \le 10$ and $M \le 20$.

For $70\%$ of the testdata, $N \le 10^3$ and $M \le 10^4$.

For $100\%$ of the testdata, $N \le 10^5$ and $M \le 2 \times 10^5$.

Translated by ChatGPT 5