Cargo Transport through Customs Unions

Assignment

A delivery truck driver has to transport a cargo from the start place in country A to the target place in country B.
There are more customs unions on the continent and each country is a member of exactly one of them.

In general, each time the truck crosses a border checkpoint between two countries the transporting company has to pay high customs duty.
Nonetheless, there are two exceptions to this rule.
First, no payment is made when the the countries sharing the border checkoint are mebers of the same customs union.
Second, no payment is made when the cargo is in so called re-entry state.
The cargo is in re-entry state at a border checkpoint if it is leaving customs union C and entering customs union D and before that it arrived to some member country of C from a member country of D, the customs duty was paid, then the cargo was transported only through member country or countries of C and now it is being transported to a member country of D. However, in the above scenario, the cargo is not in the re-entry state if the customs duty was not paid when cargo arrived from a member country of D to a member country of C.

The customs duty is the same at all borders and the task is to transport the cargo while paying minimum number of customs duties.

Image 1. Examples of problem statement and solution. The vertices represent the countries and the edges represent the border checkpoints between them. A possible optimal solution consists of red and green edges. Red edges represent customs duty payment at the border, green edges represent free crossing of the border. The membership in a particular customs union is coded by vertex colors. The start and the target countries/vertices are: a) 0 and 5, b) 0 and 4, c) upper left corner and lower right corner.

Task

There is a list of all countries on the continent. It is also known for each country which customs union it is a member of. Also a list of all pairs of countries which share common border checkpoint is given. Find the minimum number of customs duty payments needed to transport the cargo from a given country A to another given country B. All border checkpoints are considered bi-directional.

Input

The first input line contains four non-negative integers N, E, A, B separated by space and representing (in this order) the number of countries on the continent, number of pairs of countries which share common border checkpoint, the label of the start country and the label of the target country. Next, there are N lines representing the countries, each line contains two integers S, U separated by space. S is a country label in range 0, …, N−1 and U is the number of customs union which S is a memeber of. U is in range 0, …, 9, as there are always at most 10 different customs unions. Next, there are E lines representing all pairs of countries which share common border checkpoint. Each of these lines contains two labels of countries separated by space.

Some neighbour states are connected by long tunnels, therefore it is not quaranteed that the graph representing the countries and the border checkpoints between them is a planar graph. Nevertheless, the planarity is not essential in this problem. On the other hand, it is essential that the graph is sparse, that is, E ≤ 4N. It is also known that the value of N does not exceed 1×10⁶ and the value of E does not exceed 3.1×10⁶.

Output

The output consists of one text line containing one non-negative integer equal to the minimum number of customs payments needed for cargo delivery.

Examples

Example 1

Input

Output

The data and the solution of Example 1 are depicted in Image 1a).

Example 2

Input

Output

The data and the solution of Example 2 are depicted in Image 1b).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Public data