The Hobomobile

Limits: 2 sec., 256 MiB

In the kingdom of Hobbits there is very interesting road system. Each road is bidirectional, but every day there is the only allowed traffic direction and every next day this direction changes to the opposite one.

Recently, one Hobbit has constructed a car called Hobomobile. This is just a demo version, thus the car is able to start only once, i.e. if the car stops it won’t move again. Also the speed is constant and the car travels one road per day, because of the equal length of all roads in the kingdom.

The roads intersect nowhere except the cities they connect. Also it is possible for a road to connect the city with itself. Moreover there could be more than one road between a pair of cities.

You have to find the minimal number of day needed for the Hobbit to travel by his Hobomobile form the city \(A\) to the city \(B\). Note that the Hobbit could optionally wait several days to start his trip, but you should take into account them while computing the answer.

Input

The first line contains four integer numbers \(N\), \(M\), \(A\) and \(B\) separated by single spaces. Here, \(N\) is the number of cities in the kingdom. The next \(M\) lines contain the road descriptions. Each such line contains two integer numbers \(a_i\) and \(b_i\) separated by a single space. The \(i\)-th road connects cities \(a_i\) and \(b_i\). On the first day the allowed traffic direction is from the city \(a_i\) to the city \(b_i\).

Output

Print two lines. The first line should contain the minimal number of days needed for the Hobbit to get from the city \(A\) to the city \(B\) using only the valid traffic directions. If it is impossible to do this print -1 instead (quotes for clarity). The second line should contain the similar information for the case of using any road directions.

Constraints

\(1 \le N, M \le 10^5\),

\(1 \le A, B, a_i, b_i \le N\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 5 4 7 1 2 3 2 3 1 1 4 7 1	6 2