P12502 「ROI 2025 Day1」天狼星的换班

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day1 T2.** ***[Пересменка в Сириусе](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day1.pdf)*** 你有没有好奇过，为什么天狼星教育中心的两期项目之间总会隔上几天？答案很简单：员工们需要在这段时间里把宿舍楼的房间整理一新，为下一期项目做准备！ 天狼星酒店的某层楼有 $n$ 个房间，编号从 $1$ 到 $n$。每次教育项目结束后，这些房间都需要进行维修。 为此，中心雇佣了 $k$ 名员工，编号从 $1$ 到 $k$。每位员工负责一段房间范围，从 $l_i$ 到 $r_i$（包含两端），并且每人有一个固定的起点房间 $m_i$，他们必须从这个房间开始检查和维修。不同员工的负责范围可能会有重叠，甚至完全相同。 员工们会按照某种顺序从基地出发去维修房间。每次只有前一位员工返回基地后，下一位员工才会出发。 当第 $i$ 位员工出发时，他会先前往起点房间 $m_i$： - 如果这个房间仍需维修，员工会修好它，然后继续检查并维修他负责范围 $l_i$ 到 $r_i$ 内所有仍需维修的房间。完成后，他返回基地。此时，他负责的整个范围内的房间都不再需要维修。 - 如果起点房间 $m_i$ 已经被其他先出发的员工修好，员工会直接返回基地，寄希望于同事们已经顺便修好了他负责范围内的其他房间。但实际上，他负责范围内可能仍有房间需要维修。 你的任务是判断，是否能通过合理安排员工的出发顺序，让所有 $1$ 到 $n$ 的房间最终都被修好。

输入包含多组数据。第一行是一个整数 $t$ $(1 \leq t \leq 10^5)$，表示数据组数。接着是每组数据的描述。 每组数据的第一行包含两个整数 $n$ 和 $k$ $(1 \leq n, k \leq 5 \cdot 10^5)$，分别表示房间数量和员工数量。 接下来的 $k$ 行，每行包含三个整数 $l_i,m_i,r_i$ $(1 \leq l_i \leq m_i \leq r_i \leq n)$，分别表示第 $i$ 位员工负责范围的起点房间、必须开始检查的起点房间，以及范围的终点房间。 保证所有数据组的 $n$ 和 $k$ 之和均不超过 $5 \cdot 10^5$。

对每组数据，输出单独的一行。如果可以修好所有房间，输出 `YES`；否则输出 `NO`。

### 样例解释 在第一组数据中，先派第 $2$ 位员工出发，他会修好房间 $1$ 到 $3$。然后派第 $1$ 位员工出发，他前往房间 $4$，发现它仍需维修，于是修好他负责范围内剩余的房间。最终，所有房间都被修好。 在第二组数据中，无法找到一个合适的员工出发顺序来修好所有房间。 ### 数据范围 记 $N$ 为所有数据组的 $n$ 之和，$K$ 为所有数据组的 $k$ 之和。 详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $5$ | $K \leq 10\,000$，$m_i = l_i$ | | | $2$ | $5$ | $N \leq 500$，$k \leq 8$ | | $3$ | $2$ | $n \leq 18$，$K \leq 500$ | | $4$ | $12$ | $n \leq 50$，$K \leq 50$ | | $5$ | $9$ | $n \leq 150$，$K \leq 150$ | | $6$ | $8$ | $N \leq 500$，$K \leq 500$ | | $7$ | $6$ | $K \leq 10\,000$，每个员工负责的范围包含房间 $1$ 或 $n$ | | | $8$ | $18$ | $K \leq 10\,000$，每个员工负责的范围内至少有一个房间只由他负责 | | | $9$ | $3$ | 每个员工负责的范围内至少有一个房间只由他负责 | $8$ | | $10$ | $4$ | $K \leq 10\,000$，任意 $i, j$，$r_i - l_i = r_j - l_j$ | | | $11$ | $4$ | $K \leq 10\,000$，任意 $m_i$ 等于 $l_i$ 或 $r_i$ | $1$ | | $12$ | $4$ | $n \leq 10\,000$，$K \leq 10\,000$ | $0,2-6$ | | $13$ | $6$ | $K \leq 10\,000$ | $0,1-8,10-12$ | | $14$ | $14$ | 无附加限制 | $0,1-13$ |