Use Floyd's algorithm to find a cycle node. Then trace the entire cycle and mark all nodes in it. Store cycle membership as a boolean array. Once you know cycle membership, you can separate tail nodes from cycle nodes. This separation drives the case analysis. Each case has different logic.
Without this preprocessing, you would have to simulate every query, which times out. Preprocessing once lets you answer all queries efficiently.