Konigsberg Bridge

All submissions for this problem are available.
There are N islands numbered from 0 to N1 which are connected by a single bridge. Peter and Pan are located at island 0. They want to visit all islands exactly once and return back to island 0. There are K toll booths. Each toll booth has a certain range of functioning. The arguments for toll k are given as x_k and y_k. If the salesman travels from city i to j, he has to pay 1 dollar toll fee to each toll p having x_p >= i and y_p <= j. Calculate the cheapest way for the salesman to complete his tour.
Input
The first line contains T the number of test cases.
The first line of each test case contains two space seperated integers N and K.
Each of the next K lines contains 2 integers, the ith line containing x_i and y_i (0 <= x_i,y_i < N).
A blank line seperates two test cases.
Constraints
1 <= T <= 50 2 <= n <= 1000 1 <= K <= 10000
Output
Output is a single line for each test case.
Example
Input: 2 2 2 1 2 0 1 3 4 1 0 2 1 0 1 1 2 Output: 1 6
Author:  saurabh1992 
Tags  saurabh1992 
Date Added:  8022013 
Time Limit:  30 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, RUBY, GO, NODEJS, PERL, PERL6, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 