题目描述

对于一个排列 $p$，按照以下方式定义 $f(p)$：

• 对于排列中的一个元素 $p_i$，令 $a_i$ 为以其结尾的最长上升子序列长度，$b_i$ 为以其开头的最长下降子序列长度，定义其坐标为有序二元组 $(a_i, b_i)$。
• $f(p)$ 为 $p$ 中所有元素的坐标构成的集合。

例如，$f({1, 2, 5, 4, 3, 6}) = {(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (4, 1)}$。

给定正整数 $n$ 和 $n$ 个互不相同的有序二元组 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，其中 $x_i, y_i$ 均为不超过 $n$ 的正整数。

构造一个长度最小的排列 $p$，使得 $f(p)$ 包含所有 $n$ 个给定的二元组，$f(p)$ 可以包含 $n$ 个给定的二元组以外的其他元素。

若有多个长度最小的排列，输出任意一个。可以证明，在给定条件下，总是存在一个长度不超过 $3n$ 的排列。

若你输出的排列不是长度最小的排列，但是长度不超过给定参数 $lim$，也可获得部分分数。

输入格式

输入的第一行包含两个正整数 $n, lim$，分别表示二元组的数量和你构造的排列的长度上限。

接下来 $n$ 行，每行包含两个正整数 $x_i, y_i$，表示 $f(p)$ 必须包含 $(x_i, y_i)$。

输出格式

输出两行。第一行包含一个正整数 $m$，表示你构造的排列长度，你需要保证 $n \le m \le lim$。

第二行包含 $m$ 个正整数，表示你构造的排列 $p$。

样例 1

input

2 6
2 1
1 2

output

3
2 1 3

样例 2

input

2 6
2 2
2 1

output

3
1 3 2

样例 3

input

3 9
1 1
2 1
3 3

output

5
1 4 5 3 2

样例 4

input

4 12
3 1
2 4
1 4
2 3

output

7
4 6 3 5 2 1 7

样例 5

input

6 18
1 1
4 2
1 4
2 4
1 5
4 1

output

9
5 4 6 3 2 7 9 1 8

样例 6

input

8 24
1 3
3 1
2 5
2 4
5 3
3 2
1 1
4 2

output

10
5 9 8 1 2 4 7 10 6 3

样例 7

input

10 30
3 3
5 10
5 8
8 7
2 6
3 4
2 2
7 3
4 4
10 10

output

22
2 9 4 6 12 15 16 18 20 21 22 14 13 11 19 10 8 7 5 17 3 1

数据范围

对于所有数据，保证 $1 \le n \le 5000$, $3n \le lim \le 15000$, $1 \le x_i, y_i \le n$。

本题共 $6$ 个子任务：

对于每个测试点，若你成功构造了长度不超过 $lim$ 的排列，可以获得 $40\%$ 的分数；若你成功构造了长度最小的排列，可以获得 $100\%$ 的分数。对于每个子任务，你的得分为其所有测试点得分的最小值。

下发文件中的 chk.cpp 可以用于检验你的输出。