Subtask 1 (17%): 1 ≤ N ≤ 2000, 1 ≤ M ≤ 5000

Subtask 2 (29%): 1 ≤ N ≤ 50000, 1 ≤ M ≤ 50000

Subtask 3 (54%): 1 ≤ N ≤ 500000, 1 ≤ M ≤ 500000

Subtask 4 (0%): Sample Testcases