PTA 7-3 幸福小镇的故事! (最短路径直接用floyd会超时怎么办?)

7-3 幸福小镇的故事！（简单） (25 分)

在一个很远很远的地方，有一个幸福小镇！

幸福小镇的治安很不好，所以生活在镇上很不幸福！

新来的保安队队长小Z决心改变这一切，第一步要解决的是任何两个小镇之间的距离问题！

我们需要解决这个问题的简化版本：

幸福小镇可以划分为N个小小镇，从1到N编号！这些小小镇由N-1条道路连通，我们把每条道路的长度简化为1！只要在每个小小镇增派人手，就可以让小镇的治安情况变得越来越好！（题目保证两个小镇之间的道路只有一条！）

每次小Z会询问你两个小小镇的编号，请你计算出这两个小镇之间的最短路径长度！

输入格式:

第一行包含一个正整数（N<=1000），表示小小镇的个数！

接下来N-1行，每行包含两个1到N之间的整数，表示这两个编号的小小镇之间有一条路！

接下来一行包含一个整数q（q<=100)，表示询问数！

接下来q行，每行包含两个小小镇的编号，请在一行中输出这两个小小镇的最短路径长度！

输出格式:

输出答案即可！

输入样例:

在这里给出一组输入。例如：

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

输出样例:

在这里给出相应的输出。例如：

1
3
0
3
1