Subtask 1 (27%): N will not be more than 1000.
Subtask 2 (73%): N will not be more than 200000. (Original restrictions)
Subtask 3 (0%): Sample Testcases

Statement and Testdata from NWERC 2015.