In this problem in input data must be TREE, because in input write:" The input file contains full history TREE description...". But it is not a tree, because there are cycle...

Yes, I think that it is true. I used LCA-offline algorithm (I know that it is a bit complicated, but..) and got WA on 42 test many times. At the end of the contest I've made the same decision as yours.

it's impossible to describe cycle by such way of input, IMHO

The problem was redjudged, some authors got AC now

Sorry, for this mistake