给定n个整数区间(每个整数区间由两个整数left和right表示:left和right分别为区间的下边界和上边界,即整数区间可表示为:[left, right])。
定义函数f(x)为整数x属于整数区间的个数(如果x属于区间i:[lefti, righti],则显然有:lefti≤x≤righti)。
如果一个整数x比任意其他整数所属的区间个数都多(即对于任意整数y,都有f(x)>f(y)),则该整数即为可爱的整数。
现给我们一个整数k,你的任务是确定是否有可能删除一些(可能是零)整数区间,以使给定的整数k成为可爱的整数?
第一行只有一个整数t(1≤t≤1000):测试用例的数量。
对于每个测试用例:
第一行共有两个整数n和k(1≤n,k≤50)
接下来共n行,每行两个整数,第i行的两个整数分别为第i区间的下边界lefti和上边界righti,即第i区间为:[lefti, righti]。保证 1≤left≤right≤50
对于第一个测试用例,k=3,共有4个区间:[1,3],[7,9],[2,5]和[3,6],所有f(3)=3,对于任意其他整数y,都有f(y)<=2, 所以3已经是可爱的整数。
对于测试用例2和测试用例3,我们都无法通过删除一些区间,使得k为可爱的整数;
对于测试用例4,k=5,共有3个整数区间:[1,4],[6,7],[5,5],我们可以删除[1,4]区间和[6,7]区间,只保留[5,5]区间,使得f(5)=1, 对于任意其他整数y,都有f(y)=0,此时5是可爱的整数。