测试数据来自 system/2350

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　何氏家族很大，其子孙遍布全世界，如果两个何姓子孙他乡相遇，他们有多少个共同祖先呢？这是一个难题。

　　现在请你帮忙写一个查询系统，根据何氏族谱（是一棵以 1 为根的树），查询任意两个何姓人共同祖先的数目。

【输入格式】

　　第一行包含两个整数 \(N,M\)，其中 \(N\) 表示族谱中有 \(N\) 个人(编号为 \(1..N\))；
　　接下来的 \(N-1\) 行，给出族谱，每行包含两个整数：\(f,s\)，表示 \(f\) 是 \(s\) 的父亲。
　　第 \(N+1\) 行是一个整数 \(M\)，表示查询次数；
　　接下来 \(M\) 行 ，每行两个整数 \(x,y\)，要查询 \(x,y\) 的公共祖先数目。

【输出格式】

　　输出 \(M\) 行，每行一个正整数，表示对应查询的答案。

【输入输出样例】

　Input

11
1 2
1 3
2 5
2 6
5 7
6 8
6 10
8 11
3 4
3 9
5
5 10
9 8
7 5
10 11
4 9

　Output

2
1
2
3
2

【输入输出样例解释】

　　下图是样例数据对应树：

　　5 和 10 的公共祖先两个，他们是：1，2；
　　9 和 8 的公共祖先一个，他们是：1；
　　7 和 5 的公共祖先两个，他们是：1，2；
　　10 和 11 的公共祖先三个，他们是：1，2，6；
　　4 和 9 的公共祖先有两个，他们是：1，3；

【数据限制】

　　\(对于 70\%\) 的数据，满足 \(1<=N<=1000\)。
　　\(对于 100\%\) 的数据，满足 \(1<=N,M<=250000\)。

【来源】

　　Mr.he