I haven’t done the contest, but here’s how I would solve it with a simple implementation:

The statement "i \oplus j has exactly 2 set bits" means that node i has an edge to j if they differ by exactly 2 bits in their binary representation. So in one “move”, you can flip exactly 2 bits of a. Let’s find the number of bits in which a differs from b and call it x (one-line implementation: `__builtin_popcount(a ^ b)`

). If x is even, you can reach b in \frac{x}{2} moves, otherwise, it’s impossible (because you always have to flip an even number of bits). Complexity: O(1) per test case.

As a bonus: you may ask, how do we avoid the constraint that the numbers have to be less than or equal to n? We use the fact that a, b \leq n. First, we switch off the bits that are set in a but not in b. Then, we have some number y \leq a, b \leq n. Now we switch on the bits that are set in b (these two steps may be combined, it makes no difference). In both of these steps, we never exceed the maximum of a and b, so the path is always achievable.