小橙交换水果

题号：NC312241
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 有一棵 $n$ 个节点的树，节点编号为 $1$ 到 $n$ 。树上有两个水果，初始时分别位于节点 $u$ 和节点 $v$ （ $u\neq v$ ）。每次操作，小橙可以选择一个水果，将其从当前节点移动到任意一个没有水果的相邻节点（任意时刻同一个节点不能有两个水果）。
$\hspace{15pt}$ 小橙希望通过若干次操作，将两个水果的位置交换：原来在节点 $u$ 的水果最终位于节点 $v$ ，原来在节点 $v$ 的水果最终位于节点 $u$ 。
$\hspace{15pt}$ 现在有 $q$ 次询问，每次询问给出两个整数 $u$ 和 $v$ ，表示初始时两个水果的位置。对于每次询问，输出完成交换所需的最少操作次数，如果无法完成交换，输出 $-1$ 。

输入描述:

第一行输入两个整数 ，分别表示树上节点个数和询问的次数。
此后  行，第  行输入两个整数 ，表示第  条树边连接节点  和 。
此后  行，第  行输入两个整数 ，表示第  次询问两个水果的节点编号。

输出描述:

对于每一次询问，新起一行输出一个整数，表示完成交换的最少操作次数，如果无法完成交换，输出 。

示例1

输入

复制

输出

复制

6
6

示例2

输入

复制

2 1
1 2
1 2

输出

复制

-1

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。