E-良心送分题_牛客挑战赛35

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

注：本题所有边的边权均为 ${1}$ ,下文将不再提及。
给定一棵 ${n}$ 个点的树 ${G=<V,E>}$ ,现在通过以下规则创造一个 ${n\times k}$ 个点的图 ${G'=<V',E'>}$
将 ${G'}$ 的点分为 ${k}$ 组，每组 ${n}$ 个点，每个点的标号为 ${(a,b)}$ ，表示这是第 ${a}$ 组第 ${b}$ 个点。
${G'}$ 中存在边 $((a_{1},b_{1}),(a_{2},b_{2}))$ 当且仅当 ${a_{1}=a_{2}}$ 且边 $(b_{1},b_{2})∈E$
构造完 ${G'}$ 之后，我们再向其中加入另外的 ${m}$ 条边，第 ${i}$ 条边连接点 $(x_{i},y_{i})$ 和点 $({z_{i},w_{i}})$ 。
最后，请你求出点 ${(sa,sb)}$ 至点 ${(ta,tb)}$ 的最短路

输入描述:

第一行数字
接下来行，每行两个数字，表示树中的一条边
接下来行，每行四个数字，表示一条被添加的边
接下来一行四个数字。

输出描述:

一行一个数字表示答案，若与不连通则输出

示例1

输入

复制

输出

复制

备注:


保证答案在int范围内，可能有重边