题目描述

小昌和小明生活在一棵有 $n$ 个结点的树上，编号从 $1$ 到 $n$ ，树上有若干个国家。

如果一个结点连着超过两条边，那么这个结点上就会出现一个王国，编号和结点的编号相同（保证至少存在这样一个点），这个王国的首都就是这个结点。王国会秉持"先到先得"的原则尽可能地扩张自己的领土。也就是说，一个结点会被首都距离它最近的王国占领（如果有多个王国取编号最小的）。

小昌和小明的关系非常好，因此小昌会经常去拜访小明，路上可能会经过若干个王国的领土。同时为了节省时间，小昌会沿着最短的路径到达小明的家。 现在你需要回答 $q$ 次询问，给出 $u$ 和 $v$ ，假设小昌住在 $u$，小明住在 $v$ ，那么小昌在去拜访小明的路上会经过几个王国的领土？

输入格式

第一行一个正整数 $n$ ，表示树的结点数。

接下来 $n - 1$ 行，每行包含两个正整数 $x, y$，表示一条从结点 $x$ 到结点 $y$ 的边。

第 $n + 1$ 行包含一个正整数 $q$，表示询问的数量。

接下来 $q$ 行，每行包含两个正整数 $u, v$，描述了一次询问。

• $4\leq n \leq 2\times 10^5$
• $1\leq q \leq 2\times 10^5$
• $1\leq x,y \leq n$
• $1\leq u,v \leq n$

输出格式

对于每次询问输出一行，包含一个整数，表示对应的答案。

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

2
2
1
1