406824: GYM102566 A Beggars

Among the many duties of a Software Engineer at the railway company is that of managing the schedule of each beggar working at the Northern Railway Station. It is a well known fact that the beggars are resilient human beings - they do not take breaks from begging and are always onboard a train during the interval of time [0, d]; and also quite quarrelsome - it is best if they do not meet with other beggars while switching trains during the interval of time (0, d) or, even worse, inside a train.

Knowing exactly the time intervals that each of the $$$n$$$ trains stay inside the terminal, you have to find out the maximum number of beggars which can work together at the Northern Railway Station. Keep in mind that a beggar is able to switch trains instantly and will always remain inside a chosen train for the entire duration said train stays in the terminal.

The first line of the input will contain the number of test cases $$$T$$$ ($$$1 \leq T \leq 10$$$).

The first line of each test case will contain $$$d$$$ ($$$0 \leq d \leq 200$$$) the length of the daily begging session and $$$n$$$ ($$$1 \leq n \leq 20.000$$$) the number of trains.

The following $$$n$$$ lines of each test case will contain a pair of integers $$$x_i, y_i$$$, the time interval that the $$$i$$$-th train stays in the terminal ($$$0 \leq x_i < y_i \leq d$$$).

The output should contain $$$T$$$ lines, each containing the answer for a test.

1
9 7
0 2
0 2
0 3
2 5
2 9
3 9
5 9

2

Trains are

$$$1: [0-2]$$$

$$$2: [0-2]$$$

$$$3: [0-3]$$$

$$$4: [2-5]$$$

$$$5: [2-9]$$$

$$$6: [3-9]$$$

$$$7: [5-9]$$$

The following is an example scheduling of the beggars:

Beggar 1 goes on trains 1, 4, 7 [0-2-5-9]

Beggar 2 goes on trains 2, 5 [0-2-9]

Beggar 3 goes on trains 3, 6 [0-3-9]

Beggars 1 & 2 would meet on the platform at time 2, so this choice does not satisfy the constraint.

There is no valid choice of more than 2 beggars. Beggars 1 & 3 is an example valid solution.