Codeforces Round #356 (Div. 1) - D. Bear and Chase

Problem Statement:
Codeforces Round #356 (Div. 1) - D. Bear and Chase

Summary:
We are to maximise the probability of guessing the position of a target in an undirected graph, given that the procedure that we must follow is:
Step 1. Choose a node. The shortest distance to the target is revealed. We either guess where the target is, or go to step 2.
Step 2. Target moves to another node via an edge. Now choose a node again and the shortest distance to the target is revealed. Guess where the target is.
Initially each node has equal probability of containing the target. After Step 1, target moves to a neighbouring node with equal probability among the neighbours.