Max 非常喜欢下棋。世界上唯一能让他比下棋更兴奋的事情，就是为编程竞赛构思题目。这道题对他来说是一种极致的享受，因为他能够将自己的兴趣融合成一件杰作。

Max 发明了一种树坐标二维棋盘，你将在上面移动一个名为 treeshop 的棋子。形式化地，给定两个连通的无向无环图（也称为树），大小分别为 $n_1$ 和 $n_2$。treeshop 的位置由一对顶点 $(u, v)$ 定义，其中 $u$ 是第一棵树中的某个顶点，$v$ 是第二棵树中的某个顶点。

同一棵树中两个顶点之间的距离等于连接这两个顶点的唯一简单路径所包含的边数。treeshop 可以从位置 $(u, v)$ 移动到位置 $(u', v')$，当且仅当顶点 $u$ 到 $u'$ 的距离等于顶点 $v$ 到 $v'$ 的距离。显然，如果可以从 $(u, v)$ 移动到 $(u', v')$，那么也可以从 $(u', v')$ 移动到 $(u, v)$。

给定 $q$ 对位置。对于每一对位置，你需要计算 treeshop 从一个位置移动到另一个位置所需的最少移动次数。

输入格式

第一行包含整数 $n_1, n_2$ 和 $q$ ($1 \le n_1, n_2, q \le 200\,000$)，分别表示第一棵树的顶点数、第二棵树的顶点数以及需要处理的位置对数。

接下来 $n_1 - 1$ 行描述第一棵树的边。每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n_1, u_i \neq v_i$)，表示由相应边连接的顶点索引。

接下来 $n_2 - 1$ 行以完全相同的方式描述第二棵树。

随后 $q$ 行描述所有需要处理的位置对。第 $i$ 行包含四个整数 $s_1, s_2, t_1$ 和 $t_2$ ($1 \le s_1, t_1 \le n_1, 1 \le s_2, t_2 \le n_2$)，前两个整数描述初始位置，后两个整数描述目标位置。

输出格式

对于每个询问，输出一个整数。如果可以通过 treeshop 的移动从初始位置到达目标位置，则输出所需的最少移动次数。否则，输出 -1。

样例

输入 1

4 5 7
1 2
2 3
2 4
1 2
2 3
3 4
4 5
1 1 2 5
1 5 4 1
1 5 4 2
2 5 2 3
2 1 2 5
3 2 3 2
4 4 1 2

输出 1

-1
2
-1
2
3
0
1