间谍 007 发现了她最大的敌人 Dr. De Referenced Nullpointer（简称 Dr. Null）的一个阴谋：Dr. Null 企图拔掉两台 CEOI 服务器之一的电源插头。Dr. Null 正准备实施他的计划，并正设法前往服务器所在地。不幸的是，这意味着 007 必须在某个时刻离开正与她共进早餐的英俊男士。

007 和 Dr. Null 都黑入了卫星观测系统，因此他们随时都清楚对方的位置。该系统将目标区域显示为一个连通的无向图，007、Dr. Null 以及两台服务器都位于图中的节点上。请注意，这两台服务器位于相邻的节点上，因为它们在同一个服务器机房内。Dr. Null 和 007 均可在每个时间单位内沿单条边移动，也可以选择不移动。拔掉服务器的电源插头也需要消耗一个时间单位。这些移动是交替进行的，由 Dr. Null 先行动。

007 如果能抓住 Dr. Null，或者永远阻止他拔掉任何一台服务器的电源插头，则 007 获胜。当 007 到达 Dr. Null 所在的节点时，即视为抓住了 Dr. Null。007 想知道她最多可以继续享用早餐多长时间，以便无论 Dr. Null 采取何种行动，她都能确保获胜。

请帮助她编写一个程序，计算她为了确保获胜而必须结束早餐的最晚时间（即最多可以等待多少个时间单位）。请注意，在享用早餐期间，即使 Dr. Null 恰好与 007 处于同一节点，她也无法抓住任何人。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示图中的节点数和边数。节点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。

第二行包含四个互不相同的整数 $s, d, a, b$（$1 \le s, d, a, b \le N$）。它们分别表示：007 的初始位置、Dr. Null 的初始位置，以及两台服务器的位置。

接下来的 $M$ 行描述图中的边。每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le N$），表示由该边连接的两个节点。

输出格式

输出仅包含一行，即一个整数：007 最多可以继续享用早餐的时间单位数，以确保她仍能获胜。特别地，如果 007 必须在她的第一回合立即出发，则输出 0。

如果 007 根本无法获胜，则输出 -1。

数据范围

始终满足 $4 \le N \le 200\,000$，$3 \le M \le 600\,000$。

• 子任务 1（30 分）：$N \le 800$ 且 $M \le 1\,600$。
• 子任务 2（70 分）：无附加限制。

部分分说明

对于任何测试点组，如果你的程序输出的答案比（非负的）正确答案恰好少 $1$（在至少一个测试点中），且在其余所有测试点中均正确，你将获得该测试点组 $30\%$ 的分数。请注意，为了获得此部分分，如果正确答案是 0，你的程序可以输出 -1（但反之则不行！）。

样例

输入样例 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

反馈

本题提供部分反馈，即你可以看到固定测试点子集的评测结果，且公开得分会提示你的实际得分（实际得分可能会更低或更高）。