SP27340 AR2015PC - Terrorists

Terrorists! There are terrorists everywhere!!! I was shouting out loud after I had watched a few news reports about terrorism acts that had happened around my neighborhoods. I started to think that hiding at home wasn’t a good way to go. I went to police stations and asked around if I could help them prevent these issues. The police gave me pieces of information about terrorists’ plans. I ended up lying on my bed and figuring way to utilize this information. That is why I come to you. Our neighborhoods could be illustrated with intersections and roads. Terrorists usually meet up at one intersection before moving to another intersection to perform an illegal act. The given information tells us where they will meet and where they will go. Unfortunately, the certain schedules of those plans are not available and too few policemen are available lately. So, the police will not be able to set up efficient defenses to all of those acts. What they could do is set up surveillance cameras to all meet up intersections. Once a meet up is detected, policemen will go to that meet up’s destination to catch the terrorists. The policemen rarely accomplish it because they spend too long time travelling between places. Because terrorists are smart, they always use shortest route to travel between intersections. Because the policemen aren’t that smart, they need our help. For each terrorist plan, the police want us to compute the shortest distance between the meet up place and the destination. If the distance is too short, they will not spend their efforts for free. **Input** The first line of the input contains an integer **T**, the number of test sets **(1

N/A

N/A