時間制限 : sec, メモリ制限 : KB
Japanese

B: Spent Fuel Disposal

問題文

$N$ 個の下水処理施設が $M$ 本のパイプで繋がっており、$i$ 番目のパイプは $u_i$ 番目と $v_i$ 番目の施設を繋いでいます。 パイプは全て、毎秒最大 $1$ リットルの液体を流すことができます、

今、$S$ 番目の施設から $T$ 番目の施設へ工業廃水を、 $U$ 番目の施設から $V$ 番目の施設へ純水を流したいです。$S$ 番目および $U$ 番目の施設は、それぞれ工業廃水および純水を十分な量有しており、パイプで繋がっている別の施設へこれらの液体を好きに送ることができます。 また、各施設では、送られてきた液体をパイプで繋がっている別の処理施設へ流すことができます。

パイプはハイテクなので、$2$ 種類の液体を同時に好きな方向へ流すことができます。 例えば、$i$ 番目のパイプは、$u_i$ から $v_i$ へ工業廃水を、$v_i$ から $u_i$ へ純水を流すことができます。 反対に $v_i$ から $u_i$ へ工業廃水を、$u_i$ から $v_i$ へ純水を流すことも可能です。 もちろん、$2$ 種類の液体を同じ方向へ流すこともできます。

ただし、どの場合においても、$1$ つのパイプに流す液体の総量は毎秒 $1$ リットルを超えることはできません。 $S$ から $T$ へ流す工業廃水の総量と $U$ から $V$ へ流す純水の総量の合計は、最大で毎秒何リットルにできますか。 答えは整数になることが証明できるため、整数で出力してください。

制約

  • 入力は全て整数
  • $1 \leq N, M \leq 10^5$
  • $1 \leq S, T, U, V \leq N$
  • $S \neq T$
  • $U \neq V$
  • $1 \leq u_i, v_i \leq N$
  • $u_i < v_i$ ($i = 1, \ldots, M$)
  • $i \neq j \rightarrow (u_i, v_i) \neq (u_j, v_j)$
  • 全ての施設はパイプを通じて連結である

入力

入力は標準入力から以下の形式で与えられます。

$N$ $M$ $S$ $T$ $U$ $V$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$

出力

答えを1行に出力してください。

入出力例

入力例1

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

出力例1

2

例えば、$1$ から $5$、$5$ から $4$ へ工業排水を毎秒 $1$ リットル、$2$ から $3$ へ純水を毎秒 $1$ リットル流せば良いです。

入力例2

3 3 1 2 1 3
1 2
1 3
2 3

出力例2

2

$T$ と $V$ が同一の施設であるケースなどに注意してください。