For all subtasks, 1 ≤ N ≤ 100 000, 1 ≤ Q ≤ 100 000.
Subtask 1 (27%): Each city is connected by at most 2 trains.
Subtask 2 (22%): 1 ≤ N ≤ 10 000, 1 ≤ Q ≤ 10 000.
Subtask 3 (51%): No further constraints.
Subtask 4 (0%): Sample Testcases.