railway

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.