Hi, I didn't particicpate in this contest (#148 div.1) due to the need to prepare for the exam. Later today I came back to browse the problems and think about them.

I think problem E in this contest is wrong (will elaborate below), or at least, as far as the official solution (and the solution i come up with at first) concerns. The major problem is that, given the rules, there are in fact more information than could be acquired when Urpal "misses" a bus. This results in means to "forcely" get on a bus, even on some of the node the bus "does not necessarily" has to go through.

Easier illustrated than described, consider the following case:

8 9 2 8
1 3
3 6
1 7
7 4
4 8
6 8
2 3
3 4
4 5
2
1 8
2 5

The ASCII plot of this graph:

5   8
 \ / \
  4   6
  |\_ |
  |  \|
  7   3
   \ / \
    1   2

The output according to editorial's solution (and my Accepted solution):

-1

The actual solution:

2

In this case Upral starts from "2" and is going to cross the "bus route" of bus 1: 1->8. In the author's sense, when Upral takes the bus and reaches node 3, bus 1 may not be there, and he has no oppurtunity to switch route. Then again at node 4, Upral again misses bus 1 (an adversary bus 1 driver!) thus he is stuck with bus 2.

But what actually happens (if Upral is as smart as anyone on Codeforces!), is that when he takes bus 2 and get to node 3, but does not see bus 1, it actually implies that at this time bus 1 must be at node 7 (recall that each second a bus spawn from its source), and on the next time fragment when Upral gets to node 4, that bus 1 he just missed at node 3 HAS to be there as well. Therefore in this case, Upral can in fact always get to node 8, and the answer should be 2 in this sense.

I understand what the problemsetter is trying to formulate in this problem, and if nothing could be implied by "missing a bus", the solution would be perfect. But I think the assumption cannot hold under the rules, and the original solution could not handle this. (Neither could I think of any revision from the original one that handle this, though. My instinct tells me with this kind of inference, it may be too hard a problem to solve efficiently.)

A possible argument is that "when Upral is on a bus, he could not know whether another bus is at the same node UNLESS he gets off the bus; this way he won't be able to infer anything UNLESS he gets off the current bus he's on". But this does not sort out the problem either. Upral could still get off the bus and observe (wait for one second) then act accordingly.

I took noticed of this case when I was testing my solution (which operates just about the same as the author's). I hope I did not get something wrong. If there's any mistake, please kindly point it out >"<.