Busy Beaver is an avid fan of Sheet Music Boss and dreams of playing long, intricate pieces on his piano. However, with only a measly $$$10$$$ fingers, there's not much he can do. Fortunately, his friend Ditto can grow an arbitrary number of fingers on their hand, letting them play any piece imaginable.
Ditto is trying to play a song consisting of $$$N$$$ notes, numbered $$$1$$$ to $$$N$$$. To play the $$$i$$$-th note, Ditto must press key $$$k_i$$$ at time $$$a_i$$$ and let go at time $$$b_i$$$. It is guaranteed that no two notes with the same key are played at the same time. In other words, for all pairs of notes $$$(i,j)$$$ where $$$k_i=k_j$$$, either $$$b_i\le a_j$$$ or $$$b_j\le a_i$$$.
Ditto plans to use a single hand with $$$F$$$ fingers, numbered left to right from $$$1$$$ to $$$F$$$, to play the song. They want to assign the finger $$$f_i$$$ to the $$$i$$$-th note. Ditto can play the song if they can assign a finger to each note to satisfy the following criteria:
- At no point in time do their fingers cross. Formally, for all pairs of notes $$$(i,j)$$$ where there exists a time $$$t$$$ where $$$a_i \lt t \lt b_i$$$ and $$$a_j \lt t \lt b_j$$$, if $$$k_i \lt k_j$$$, then $$$f_i \lt f_j$$$.
Ditto is allowed to delete up to $$$M$$$ notes from the song, where $$$M$$$ is $$$\mathbf{0}$$$ or $$$\mathbf{1}$$$. Find the minimum number of fingers they need on their hand in order to play the rest of the song. In other words, find the smallest $$$F$$$ where there exists a finger assignment $$$f$$$ that satisfies the above criteria.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\le T\le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$1\le N\le 2\cdot 10^5$$$, $$$M=0$$$ or $$$1$$$).
The $$$i$$$-th of the next $$$N$$$ lines contains three integers $$$k_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$1\le k_i \le 10^9$$$, $$$1\le a_i \lt b_i \le 10^9$$$) — meaning that the $$$i$$$-th note uses key $$$k_i$$$ from time $$$a_i$$$ to time $$$b_i$$$.
It is guaranteed that no two notes with the same key are played at the same time and the sum of $$$N$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, print the minimum number of fingers Ditto needs on their hand so that after at most $$$M$$$ note deletions, there exists a satisfactory finger assignment.
There are three subtasks for this problem.
- ($$$10$$$ points): The sum of $$$N$$$ over all test cases does not exceed $$$10^3$$$ and $$$M=0$$$.
- ($$$20$$$ points): $$$M=0$$$.
- ($$$70$$$ points): No additional constraints.
55 03 3 65 2 56 5 61 1 41 5 75 12 1 610 1 64 5 98 5 96 8 104 11 1 22 1 21 3 42 3 41 06 2 51 16 2 5
33210
The notes for the first test case are shown below. The x-axis is the key pressed, and the y-axis is the time interval the note is pressed. The minimum number of fingers required is $$$3$$$ — each note is labeled with a finger to achieve this.
The notes for the second test case are shown below. Deleting either the yellow or blue note would make $$$3$$$ fingers sufficient, and this is optimal.
