시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Spy 007 has uncovered a plot of her greatest enemy, Dr. De Referenced Nullpointer (short: Dr. Null): Dr. Null wants to pull the power plug of one of the two CEOI servers. Dr. Null is just about to carry out his plan and trying to make his way to the servers. Unfortunately, this means that 007 at some time must leave the handsome man with whom she is currently having breakfast.

Both 007 and Dr. Null have hacked a satellite observation system, so they always know each other’s position. This system shows the target area as a connected undirected graph, with 007, Dr. Null, and each server being located at nodes. Note that the two servers are on adjacent nodes, as they are in one server room. Both Dr. Null and 007 can move along a single edge in one time unit, but do not have to move. Pulling the power plug of a server also takes one time unit. These moves are taking place alternatingly, with Dr. Null moving first.

007 succeeds if she either catches Dr. Null or forever prevents him from pulling the power plug of a server. 007 catches Dr. Null when she reaches the node where Dr. Null is located.

007 wants to know how long she can maximally remain at her breakfast so that she can be certain to succeed no matter what Dr. Null does.

Help her and write a program which computes the maximum number of time units after which she must leave breakfast in order to succeed. Note that while having breakfast she cannot catch anybody, even if Dr. Null should happen to be at the same node as 007.

입력

The first line contains two integers N and M, the number of nodes and edges in the graph, respectively. Nodes are numbered from 1 to N, edges are numbered from 1 to M.

The second line contains four mutually different integers s, d, a, b (1 ≤ s, d, a, b ≤ N). They specify the following nodes: the initial location of 007, the initial location of Dr. Null, and the locations of the two servers.

The following M lines describe the edges in the graph. Each of these lines contains two integers u and v (1 ≤ u, v ≤ N), specifying the nodes connected by the edge.

출력

Your output should consist of a single line, with a single integer: the maximum number of time units 007 may remain at her breakfast so that she is still able to succeed. In particular, if 007 has to leave at her first turn, output 0.

If 007 is not able to succeed at all, output −1.

제한

It always holds that 4 ≤ N ≤ 200 000, 3 ≤ M ≤ 600 000.

점수

For any test case group for which your program’s output is 1 less than the (non-negative) correct answer in at least one of the cases of this group and correct in all other cases, you will be awarded 30% of the points of the test case group. Note that for obtaining this partial score, your program may output −1 if 0 were the correct answer (but not the other way around!).

서브태스크

번호 제한
1 30

N ≤ 800 and M ≤ 1 600

2 70

No further constraints.

예제 입력 1

6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

예제 출력 1

1

예제 입력 2

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4

예제 출력 2

0

채점 및 기타 정보

  • 예제는 채점하지 않는다.