SP14034 VPL1_AD - Autumn Leaves

秋天是一个特殊的季节，因为这时所有的树叶都会掉落。有时候，树叶会落到不太理想的地方，比如蚂蚁的花园。一天，蚂蚁 Andy 在花园里玩耍，正巧秋天来临，树叶纷纷飘落在 Andy 的花园里。Andy 赶紧跑回家中，当树叶停下了，他出来一看，却发现不仅有树叶，还有树枝。众所周知，蚂蚁最多能搬运相当于自己体重十倍的物体，但树枝实在太重了，于是 Andy 决定只清理树叶，留下树枝。然而这带来了问题，因为 Andy 只能跳过最多 K 根树枝。由于 Andy 十分懒，所以他希望找到一条清理树叶的最佳路径，但他不知从何下手，于是请求你的帮助。Andy 总是从 (0, 0) 出发（他的家），不用返回，最后一片树叶是路径的终点，但他必须至少拜访一次每片树叶。为了简单起见，树叶编号从 1 到 N，并且 Andy 的家是编号 0。请注意，像其他蚂蚁一样，Andy 不能绕过障碍物，而只能选择跳过树枝。

第一行输入一个整数 $T$，表示测试用例的数量。接下来，每个测试用例以三个整数 $N$、$M$ 和 $K$ 开始，分别表示花园里的树叶数、树枝数，以及 Andy 能跳过的最大树枝数。接下来的 $N$ 行，每行包含两个整数 $X_i, Y_i$，表示第 $i$ 片树叶的位置。接着是 $M$ 行，每行有四个整数 $X1_i, Y1_i, X2_i$ 和 $Y2_i$，代表第 $i$ 根树枝的起始和结束坐标。

对于每个测试用例，输出格式为 "Scenario #i: "，其中 $i$ 表示当前测试用例的编号（从 1 开始），后面接上 Andy 清理所有树叶所需的最短距离。接下来输出一行，表示 Andy 的行走路线。如果最短距离有多条路径，则输出字典序最小的那条。如果没有符合要求的路径，输出 `-1`。

- **子任务 1 (10%)** - $1 \le T, N, K \le 4$ - $M = 0$ - $-1000 \le X_i, Y_i \le 1000$ - **子任务 2 (15%)** - $1 \le T, N, K \le 10$ - $M = 0$ - $-1000 \le X_i, Y_i \le 1000$ - **子任务 3 (25%)** - $1 \le T, N, M, K \le 4$ - $-1000 \le X_i, Y_i \le 1000$ - $-1000 \le X1_i, Y1_i, X2_i, Y2_i \le 1000$ - **子任务 4 (50%)** - $1 \le T, N, M, K \le 10$ - $-1000 \le X_i, Y_i \le 1000$ - $-1000 \le X1_i, Y1_i, X2_i, Y2_i \le 1000$ **本翻译由 AI 自动生成**