文理学院程序设计在线练习


Volunteering

Time Limit: 3 Second(s)    Memory Limit: 32 MB

Total Submission(s): 0   Accepted Submission(s): 0
Problem Description

As a college student, Lijiang decided to increase her synthetical grade by volunteering. She needs to complete the task of solving traffic difficulties for tourists.
There are N areas in the ACM(Ancient Country of Magic).
There is an ancient subway system in the ACM. There are N-1 tracks, and track i connects directly between two different regions, ui and vi. all regions are connected by these tracks.
There are M subway routes, some of them may be the same. subway i goes back and forth between ai and bi, runs on the shortest path between them, and allows passengers to get on and off in each stop between ai and bi (including ai and bi).
As a beautiful country, there are many tourists visiting the country on the annual national day. However, these newcomers will not use satellite navigation, and can only turn to volunteer Lijiang. This time, Q tourists came to ask Lijiang.
The ith visitors will ask Lijiang whether the area pi and qi are the two stations on a certain subway line. If it is not answer 0, if so, answer there are how many such subway lines.
However, Lijiang is a road fool. If there is one mistake, the volunteer scores will be gone. Please help Lijiang so that she can answer all the questions correctly.

Input

The first line of data is a positive integer number T, which indicates that there are T test cases.
In each set of data: the first line are three integers N, M, Q, representing N areas of ACM, M subway lines in ACM, and Q tourists asking for directions to Lijiang.
Next, N-1 lines, each row has 2 numbers ui and vi, representing a track between ui and vi.
Next, M lines, each row of 2 figures ai and bi, represents a subway line between ai and bi.
Next, Q rows, each row of 2 figures pi and qi, represents tourists asking about area pi and qi.
It is guaranteed:



Output

For each query output an integer representing the answer.

Sample Input
1
4 2 3
1 2
2 3
1 4
2 4
1 3
1 3
1 2
3 4
Sample Output
1
2
0
Hint




here is the map of the ACM.
there are two subway lines 1<->2<->3 and 2<->1<->4
from 1 to 3, you can take subway green
from 1 to 2, you can take subway green and red
neither subway green nor subway red can take you from 3 to 4.

Source

2018市赛