Problem : 93 - The BUS

Problem Statistics

Solved Member: 1　　Submission: 1　　User Tried: 1

Statement:

就你所知，The Bus是一題簡單的問題，你輕鬆秒掉了它並拿走了1500瀚瀚幣的獎金。但是你的同學們最近為了公車的問題而煩惱著。

經過了宅心仁厚的瀚瀚國王整治之後，整個國家的城市已經被連通了。由於瀚瀚國王是個每天請公假在打Kingdom Rush的昏君，因此整個國家的道路設施並不是很發達，連通度非常的低。任意兩個城市之間只有一條路徑連通而已。

有一天，你的 M 個同班同學到了瀚瀚王國去旅行，卻發現他們被困在王國裡面，不知道怎麼出去。第 i 個同學想搭瀚瀚國的公車從 Si 城市到 Ei。

於是住在瀚瀚國的你，熟知了每一班公車的路線，決定要盡自己嚮導的責任，幫助你的同學們脫困！

瀚瀚國有一條不成文的規定，就是城市與城市之間的道路由於太偏僻了，公車並不會停下來。也就是說，你只有在都市的地方才可以轉乘其他公車。你想知道，每位同學最少要轉幾次車才能夠到達他們想到的目的地。

Input:Output:

第 1 行有 3 個正整數，N,T,M，分別代表城市的數量，公車的班數，以及你有幾個同學迷了路。城市由 1編號到 N 。
接下來有 N-1 行，每行有兩個數字 U,V ，代表在 U 城市以及 V 城市之間存在一條道路。
接下來有 T 行，每行有兩個整數 X,Y ，代表有一班公車的起點是 X ，終點是 Y 。
接下來有 M 行，每行有兩個整數， Si,Ei ，代表第 i 位同學想從城市 Si 走到 Ei。

N,T,M ≤ 10000
25%滿足：N,T,M ≤ 1000
25%滿足：瀚瀚國的所有路徑連起來是一條直線

輸出有 M 行，每一行有一個整數，代表你同學最少需要搭幾班公車才能夠到他要到的目的地。
如果同學永遠沒有辦法到目的地，你可以輸出 -1 就好了，代表你不想幫他了！

Sample Input:Sample Output:

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

1
-1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	65536kb
1	500ms	65536kb	5
2	500ms	65536kb	5
3	500ms	65536kb	5
4	500ms	65536kb	5
5	500ms	65536kb	5
6	500ms	65536kb	5
7	500ms	65536kb	5
8	500ms	65536kb	5
9	500ms	65536kb	5
10	500ms	65536kb	5
11	500ms	65536kb	5
12	500ms	65536kb	5
13	500ms	65536kb	5
14	500ms	65536kb	5
15	500ms	65536kb	5
16	500ms	65536kb	5
17	500ms	65536kb	5
18	500ms	65536kb	5
19	500ms	65536kb	5
20	500ms	65536kb	5