CF1297F Movie Fan

最近，Polycarp一直是电影新奇事物的粉丝，并努力不错过它们！ 在不久的将来，$n$部新电影将上映：其中第i部电影将从$a_i$到$b_i$播出。这意味着，如果Polycarp想在电影院观看第i美元的电影，他必须在从a美元到b美元（含）的时间段内观看。 如果波利卡普可能没有机会在电影院看电影，那么他可以在第二天通过在线服务观看电影。当然，这对Polycarp来说是一个不利的结果，因为全世界都有时间在社交网络上讨论这部电影！ Polycarp每天只能看价值不超过百万美元的电影。帮助Polycarp找到一个电影观看时间表，这样每部电影都会在电影院观看。如果这样的时间表不存在，那么Polycarp想看电影，这样： -对于他没有时间在电影院看的每一部电影，我们都会找到从放映结束到Polycarpus看电影的天数， -前一点的最大值应尽可能小。

第一行包含一个整数$t$（$1\le t\le 10^4$）——输入中的测试用例数。以下是对$t$测试用例的描述。 每个测试用例的第一行包含两个整数$n$和$m$（$1\le n\le 2\cdot 10^5$，$1\le m\le 10^9$）——Polycorp每天可以观看的电影数量和最大电影数量。 在接下来的$n$行中，电影本身由一对整数$a_i$、$b_i$（$1\le a_i\le b_i\le 10^9$）描述，每行一个，这是第$i$部电影的第一天和最后一天。 保证输入中所有测试用例的值$n$之和不超过$2\cdot 10^5$。

按照给定测试用例在输入中出现的顺序打印其$t$答案：第$i$个答案应由两行组成。在每个测试用例答案的第一行打印整数$d$： -如果存在在播放期间观看所有电影的时间表， -$d>0$，如果不存在这样的时间表——在这种情况下，$d$等于播出结束后所有观看“延迟”中最大值的最小值。 在每个测试用例答案的第二行中，打印$n$正整数$t_1，t_2，\dots，t_n$，其中$t_i$是Polycarp需要在最佳时间表中观看第$i$部电影的天数。 如果有几个答案，请打印其中任何一个。