3739. 网格上的路径

【题目描述】

在一个 $n×n$ 的网格上共有 $m$ 个点，每条边的长度为 $1$ 。现在你要从$(1,1)$出发，并沿着网格的边走过所有点，最后到达$(n,n)$。请你给出一种行走顺序，使得你走过的总长度不超过 $\lfloor (n+m)\sqrt{n}+2n\rfloor$

【输入格式】

第一行两个整数 $n,m$ 。

接下来 $m$ 行，每行两个整数 $x,y$ ，表示一个点$(x,y)$。保证 $1≤x,y≤n$

【输出格式】

首先输出一个整数表示你给出的方案中走过的总长度。

之后，你应该输出$[1,m]$的所有数恰好一遍，表示在你给出的方案中先后经过的 $m$ 个点的编号。

【样例输入】

3 2
2 2
2 3

【样例输出】

4
1 2

【样例说明】

一种方案是：

$(1,1)\ ->\ (2,2)\ ->\ (2,3)\ ->\ (3,3)$

总长度为 $4$ ，而 $\lfloor (n+m)\sqrt{n}+2n\rfloor=14$

【数据规模与约定】

对于$40\%$的数据，$1≤n≤100$

对于$100\%$的数据，$1≤n≤10^9\ ,\ 1≤m≤\min\{n^2,10^6\}$

【来源】

$rsr$