Problem: The Forest 1.0

时间限制：1000ms

空间限制：256MiB

Description

​ 原力清理大师在外出探索的时候，在森林里迷路了。晚上，坐在篝火边烤火的时候，他突发奇想，要是所有的树都能连在一起，他不就能顺着树爬出森林了吗O(∩_∩)O。

​ 说干就干，回到家后，原力清理大师决定进行一项实验：现在，原力清理大师共有 $n$ 棵树，每棵树都为满二叉树，根节点为 $1$ 号结点，其余结点按照层序遍历顺序依次标记为 $2,3,...$ 号。现定义合并操作如下：

​ 要将树 $a_i$ 的 $b_i$ 号结点与树 $a_j$ 的 $b_j$ 号结点合并（$1\leq i, j\leq n$ 且 $i != j$ ），操作如下：

​ ①将两个结点直接合并为一个结点。

​ ②将树 $a_i$ 上结点 $b_i$ 到其根节点最短路径上所有的边变换方向，或将树 $a_j$ 上结点 $b_j$ 到其根节点最短路径上所有的边变换方向。

​ 可以证明在完成以上操作后，合并后的图仍然为一棵树。

​ 定义每一次操作的代价为该次操作所变换的边的数量。现在，对于这 $n$ 棵树，原力清理大师发现有 $m$ 个关系，每个关系包含四个整数 $a_i, a_j, b_i, b_j$（$1\leq i, j\leq n$ 且 $i != j$ ） ，表示树 $a_i$ 的 $b_i$ 号结点与树 $a_j$ 的 $b_j$ 号结点可合并。

​ 原力清理大师发现高估了自己的行动力，他实在是没那么多时间把这些树都合并成一棵树/(ㄒoㄒ)/~~。现在他会问你将树 $a_i$ 与树 $a_j$ 合并到同一棵树内所需要的最小代价为多少，请你帮帮马上要被累死的原力清理大师吧( ఠൠఠ )ﾉ。

Input Format

​ 第一行两个正整数 $n,m$ ，代表树的数量和关系的数量。

​ 接下来 $m$ 行，每行四个正整数 $a_i, a_j, b_i, b_j$（$1\leq i, j\leq n$ 且 $i != j$ ），代表树 $a_i$ 的 $b_i$ 号结点与树 $a_j$ 的 $b_j$ 号结点可合并。在 $1.0$ 版本中，保证 $b_i = b_j$

​ 接下来 $1$ 行，两个正整数 $st, ed$（$1\leq i, j\leq n$ 且 $i != j$ ），代表原力清理大师向你询问将树 $st$ 与树 $ed$ 合并到同一棵树内所需要的最小代价为多少。

Output Format

​ 输出共 $1$ 行一个正整数，代表所需要的最小代价；若这两棵树最终无法合并，则输出 $-1$ 。

Data Range

• $1 \leq n, m \leq 1e5$
• 对于任意 $1\leq i\leq n$ ，有 $1 \leq a_i, st, ed\leq n$ ， $1 \leq b_i\leq 1e5$

Input Example #1：

3 2
1 2 2 2
2 3 4 4
1 3

Output Example #1：

3

Explanation

先将第 $1$ 棵树和第 $2$ 棵树合并，再将第 $2$ 棵树和第 $3$ 棵树合并即可。可以证明上述代价是最小的(╹ڡ╹ )。

保护森林，熊熊有责( •̀ ω •́ )y