「ROI 2025 Day1 T2」天狼星换班

题目描述

你有没有好奇过，为什么天狼星教育中心的两期项目之间总会隔上几天？答案很简单：员工们需要在这段时间里把宿舍楼的房间整理一新，为下一期项目做准备！

天狼星酒店的某层楼有 $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
5 2
3 4 5
1 3 3
5 3
1 2 4
2 4 5
3 3 3

输出

YES
NO

样例解释
在第一组数据中，先派第 $2$ 位员工出发，他会修好房间 $1$ 到 $3$。然后派第 $1$ 位员工出发，他前往房间 $4$，发现它仍需维修，于是修好他负责范围内剩余的房间。最终，所有房间都被修好。

在第二组数据中，无法找到一个合适的员工出发顺序来修好所有房间。

数据范围与提示

记 $N$ 为所有数据组的 $n$ 之和，$K$ 为所有数据组的 $k$ 之和。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。