The Last Droid

The droid R2-D2 is travelling in space with a special mission. In space, there are $N$ planets (numbered $1$ through $N$) and $M$ bidirectional space highways. Each space highway connects two planets and in order to use it, R2-D2 needs to have a sufficiently high *status level*. The droid’s mission consists of $Q$ stages. In each stage, there are two planets $x$ and $y$ such that the droid should