UVA10148 Advertisement

娱乐部门已经决定，它必须更有利可图，它想在当地公园一个受欢迎的慢跑小道上出售广告位。他们沿着小路建了许多广告牌（广告的特殊标志），并决定出售这些广告牌上的广告位。广告牌均匀地分布在慢跑路径上，它们拥有连续的整数编号，这些编号与它们在路径上的顺序相对应。每块广告牌上最多只能放一个广告。 一个特定的客户希望在这些广告牌上购买广告位，但需要保证每个慢跑者在沿着这条路跑步时至少会看到 $k$ 次广告。然而，不同的慢跑者沿着这条路的不同部分跑。 对慢跑者的采访显示，他们每个人都选择了一段他/她喜欢每天跑步的路径。由于广告商只关心慢跑者看到的广告牌，每个慢跑者的路径可以通过跑步过程中看到的广告牌序列来识别。考虑到广告牌编号是连续的，记录每个慢跑者看到的第一个和最后一个广告牌号码就足够了。 不幸的是，对慢跑者的采访也表明，一些慢跑者跑得不够远，看不到 $k$ 个广告牌。有些人的情况非常糟糕，以至于他们只能看到一个广告牌（即他们路径的第一个和最后一个广告牌编号是相同的）。由于体形不佳的慢跑者不会看到 $k$ 个广告牌，客户要求他们在他们所在路段的每个广告牌上都看到广告。虽然不如他们看到 $k$ 个广告那么好，但这已经是最好的了，足以让客户满意。 为了降低广告成本，客户雇佣你来找出如何减少他们需要支付的广告牌数量，同时满足规定的要求。

输入的第一行包含一个整数，表示输入中测试用例的数量。然后有一个空白行，每个测试用例由空白行分隔。 每个测试用例输入包含两个用空格分隔开的整数 $k,n(1\le k,n\le 10^3)$。$k$ 是每个慢跑者必须看到的最小广告数量，$n$ 是慢跑者的总数。 接下来的 $n$ 行描述了每个慢跑者的路径。每行包含两个整数 $a_i$ 和 $b_i$（两个数字的**绝对值**都不大于 $10^4$）。$a_i$ 表示慢跑者 $i$ 看到的第一个广告牌号码，$b_i$ 表示该慢跑者看到的最后一个广告牌号码。跑步时，慢跑者 $i$ 会看到广告牌 $a_i,b_i$ 和它们之间的所有广告牌。

每一个测试点的第一行，你需要输出一个整数 $m$。这个数字给出了为了满足客户的要求，广告牌上应该放置的最小广告数量。然后输出共 $m$ 行，每行一个数字。这些数字（要求按升序排列）给出了客户应该放置广告的广告牌编号。 **在测试用例之间打印空行。**