Ssi Ssi
InterviewTime limit2sMemory limit256 MB
Given M facts that two people have a certain kinship distance, answer Q queries asking the distance between two people, or -1 if it cannot be determined.
- Level
Medium6 of 10
- Topics
- Graph, Shortest path, Sorting, Implementation
- Solved
- No attempts yet
Problem
The clan with the surname 'Ssi' has N people in the world. May 11, 2019 is the day when every member of the 'Ssi' clan gathered in one place.
For one person, though, it is a painful day. 'Ssi Ssi', whose surname is Ssi and given name is also Ssi, must complete the genealogy of the 'Ssi' clan after the gathering ends.
Everyone in the 'Ssi' clan is secretive and very reluctant to introduce themselves directly. By eavesdropping on M conversations in total, 'Ssi Ssi' could hear how two people addressed each other and figure out their degree of kinship.
Tomorrow the great elder will come to inspect the genealogy before it is printed, and to pass the inspection 'Ssi Ssi' must quickly determine how many degrees of kinship separate any two people a and b. For convenience people are represented by numbers, from 1 to N in the order they attended today's gathering.
If even one inspection is failed, 'Ssi Ssi' faces being cast out of the family. Having not yet memorized all the connections, 'Ssi Ssi' is in danger at this rate. Help 'Ssi Ssi' pass all Q inspections.
Input
The first line gives the population N of this surname and the number of conversations overheard, M. (2 ≤ N ≤ 200, 1 ≤ M ≤ 20,000)
The next M lines each give two people a and b, and their degree of kinship k. (1 ≤ a, b ≤ N, 1 ≤ k ≤ 10)
The same conversation may be overheard multiple times, and there is no case of overhearing a monologue in which someone talks to themselves. (The degree of kinship between two people does not change during a conversation.)
The number of inspections Q is given, followed by Q (1 ≤ Q ≤ 100,000) lines, each giving two people x, y (x≠y) whose degree of kinship must be determined.
Output
Over Q lines, output the answer to each inspection. If the degree of kinship cannot be determined, output -1.