All submissions for this problem are available.
There are N islands numbered from 0 to N-1 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.
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.
1 <= T <= 50 2 <= n <= 1000 1 <= K <= 10000
Output is a single line for each test case.
Input: 2 2 2 1 2 0 1 3 4 1 0 2 1 0 1 1 2 Output: 1 6
|Time Limit:||30 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, RUBY, GO, NODEJS, PERL, PERL6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.