题目描述

小月所在的通信网络是一张包含 $n$ 个结点、$m$ 条边的连通$^{\texttt{[1]}}$无向图。结点的编号依次为 $1,2,\dots,n$。图中不含自环和重边。 结点 $a$ 和结点 $b$ 各有一座信号塔。两座信号塔在时刻 $0$ 同时发出各自的信号。每种信号都会沿所有边传播，第一次到达某个结点的时刻等于从对应信号塔到该结点最少需要经过的边数。 一个结点的时差，定义为两种信号第一次到达它的时刻之差的绝对值。一条路径的时差，定义为路径上所有结点时差的最大值，包括起点和终点。 小月想选择一条从结点 $s$ 到结点 $t$ 的简单路径$^{\texttt{[2]}}$，使它的时差尽可能小。请输出她能够得到的最小时差。当 $s=t$ 时，路径只包含该结点。 【名词解释】 连通图$^{\texttt{[1]}}$：如果图中的任意两个顶点之间都存在路径相连，则称这个图是连通图。 简单路径$^{\texttt{[2]}}$：图上任意两个顶点之间的路径，不经过重复的顶点和边。官方中文

输入格式

第一行输入六个整数 $n,m,a,b,s,t\left(2 \leqq n \leqq 2 \times 10^5;\ n-1 \leqq m \leqq \min\left(3 \times 10^5,\tfrac{n \times (n-1)}{2}\right);\ 1 \leqq a,b,s,t \leqq n;\ a\neq b\right)$，表示结点数量、边的数量、两座信号塔所在结点的编号、所选路径起点和终点的编号。 此后 $m$ 行，第 $i$ 行输入两个整数 $u_i,v_i\left(1 \leqq u_i,v_i \leqq n;\ u_i\neq v_i\right)$，表示第 $i$ 条无向边连接结点 $u_i$ 和 $v_i$。保证图连通，且没有自环和重边。官方中文

输出格式

输出一个整数，表示从 $s$ 到 $t$ 的路径可以取得的最小时差。官方中文