Misha, Grisha and Underground

Source: Codeforces 832D

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
   • What kind of graph is described in the problem?

2. How many cases arise from each query?

3. In each of these cases, we are interested in the edges common to two paths. How can we decompose the paths to highlight the edges in common?
   • Other group members: devise a formula for the number of edges in common.
   • Reflector: devise some challenging configurations of the three vertices to test the correctness of the formula.
   • Optional: can you prove the correctness of your formula?
4. Design an algorithm to solve the problem.
   • What preprocessing is needed to support the implementation of your formula?

5. Analyse the time complexity of your algorithm and estimate its running time.

6. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
7. Submit your program for judging!
   • Debug as required.