U394720 花园杂草

学校花园里的杂草又长了许多，教导主任于是派Rugu作为组长带领一帮值日生去拔杂草。但是马上就要放学了，Rugu想在最短的时间里拔掉所有杂草。(注:P1433 吃奶酪的变式题)。

在一个N×M的花园中有T株杂草，花园左上角为入口，右下角为出口，Rugu从入口进入后须拔掉所有的杂草后从出口离开，我们要帮Rugu给出花费体力与时间最小的拔草顺序。

第一行T,N,M分别代表杂草总数与花园的长与宽。 接下来的T行有Xi,Yi，分别为的i个杂草的位置。

输出最短路径(利用直线距离公式)，包括起点到第一株草和最后一株草到终点，依次拔第i株草，杂草序号之间用->连接。

$$1＜N,M≤1000； 1＜T≤20； 1＜Xi≤N； 1＜Yi≤M；