Submit Best Submissions All Submissions

79. On the Road to LCPC


Problem Statement:
Nicole Hosh is a member in the media core team in the ACPC from Syria. She was visiting the LCPC 2012 (Lebanese Collegiate Programming Contest) and met Mohamed Mahmoud Abd El-Wahab (AKA fegla) (an ICPC world finalist himself, who participated in the 2002 ICPC in Hawaii and coached teams to the ICPC in the 2004 ICPC in Prague, 2006 ICPC in Texas, 2008 ICPC in Banff, 2010 ICPC in Harbin, 2011 ICPC in Orlando, 2012 ICPC in Warsaw and 2013 ICPC in St. Petersburg with two teams) who was the chief judge in the same contest. They became friends very quickly and are now very close to each other.

This year Nicole is attending the LCPC, but there is one problem, due to the current situation in Syria and north Lebanon, the streets aren't very safe. So she wants to minimize the number of times she has to travel from town to town (minimize the number of roads), starting from a town in Syria and ending in a town in Lebanon. She still hasn't figured out which town to start her journey from in Syria and which town should she meet with Fegla in Lebanon in.

The good news is that Nicole is quite good with data-structures, which led her to notice that the streets between the different towns in Lebanon and Syria form a tree structure, where the towns are considered the nodes in the tree, and the roads representing the edges. So given the towns and roads between them, you need to answer multiple queries each listing a starting town and a destination town and asking for the minimum number of times she has to travel between two different towns.


Input Format:
Your program will be tested on one or more test-cases. The first line of the input will be a single integer T, the number of test-cases (1 ≤ T ≤ 100). Followed by T test-cases.

Each test case starts with a line containing two space separated integers N Q, representing the number of towns and the number of queries in the test-case. (1 ≤ N, Q ≤ 105)

N-1 lines follow, each containing two space separated integers Fr To, representing that there is a road between town Fr and town To. Roads are bi-directional, and the towns and roads form a tree. (1 ≤ Fr, To ≤ N, Fr ≠ To)

Q lines follow, each containing two space separated integers Fr To, representing a query asking about the minimum number of times she has to travel between town Fr and town To. (1 ≤ Fr, To ≤ N, Fr ≠ To)


Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1), then Q lines follow, each containing a single integer that is the minimum number of times of travel required for each query.


Sample Input:
1 6 2 1 6 1 2 1 3 2 4 2 5 4 5 5 6


Sample Output:
Case 1: 2 3





Added by: ahmed_aly
Added at: 2014-04-27 04:52:04 UTC
Time Limit: 3 seconds
Partial score: No
Source:ACM Jordanian Collegiate Programming Contest 2013