线段匹配
时间限制:1秒 内存限制:256M
【题目描述】
小沐同学手上有两类线段,分别为A线段和B线段。
A线段的有 \(n\) 种,第i种有 \(s_i\) 条,其左端点和右端点为 \(a_i\) 和 \(b_i\),他们都是 \(10^9\) 范围内的正整数,且一定有 \(a_i≤b_i\)。B线段的有 \(m\) 种,第 \(i\) 种有 \(k_i\) 条,其左端点和右端点为 \(l_i\) 和 \(r_i\),他们也是 \(10^9\) 范围内的正整数,且一定有 \(l_i≤r_i\)。小沐同学还规定,如果一条A线段 \((a_i,b_i)\) 能匹配一条B线段 \((l_j,r_j)\),当且仅当 \(l_j≤a_i≤b_i≤r_j\)。
现在小沐需要你判断能否为所有的A线段都指定一条与之匹配的B线段。注意,无论是A线段还是B线段,每条都只能匹配一次,且仅能匹配一次。
【输入格式】
输入的第 1 行是一个整数 \(T\),表示数据组数。每组数据的第 1 行有两个整数 \(n,m\),分别表A类线段和B类线段的种类数。接下来 \(n\) 行,每行 3 个整数 \(a_i 、b_i 、s_i\),描述一种A类线段。接下来 \(m\) 行,每行三个整数 \(l_i 、r_i 、k_i\),描述一种B类线段。
【输出格式】
仅输出共 \(T\) 行,每行一个字符串,若可以实现则输出 Yes,否则输出 No。
【输入输出样例】
Input
3
2 2
1 4 2
3 5 1
1 4 2
2 5 1
3 2
1 3 1
2 4 1
3 5 1
1 3 2
2 5 1
2 2
1 2 2
1 2 1
1 2 1
1 2 2
Output
Yes
No
Yes
【数据限制】
对于 \(100\%\) 的数据,\(2≤N,M,s_i,k_i≤5000\)。
【来源】
Mr.he