题目描述

$Karel$是一个生活在矩形坐标系中的机器人，每个位置由一组整数坐标$（x和y）$表示。你的任务是设计一个程序，帮助$Karel$捡起放置在其世界中的若干个蜂鸣器。为此，你必须引导$Karel$到达每个蜂鸣器所在的位置。你的工作是编写一个计算机程序，找出$Karel$从起始位置出发，访问每个蜂鸣器后再返回起始位置的最短路径长度。

$Karel$只能沿着x轴和y轴移动，不能斜着移动。从一个位置$（i, j）$移动到相邻位置$（i, j+1）$、$（i, j-1）$、$（i-1, j）$或$（i+1, j）$的代价为$1$。

可以假设$Karel$的世界不超过$20×20$的方格，且需要捡起的蜂鸣器不超过$10$个。每个坐标以$（x, y）$对的形式给出，其中每个值的范围是$1$到对应坐标系方向的尺寸大小。

输入

首先有一行包含一个整数，表示需要帮助$Karel$处理的场景数量。对于每个场景，首先有一行包含两个整数（$x$尺寸和$y$尺寸），表示世的大小。接下来一行包含两个数，表示$Karel$的起始位置。再接下来一行包含一个数，表示蜂鸣器的数量。对于每个蜂鸣器，有一行包含两个数，表示每个蜂鸣器的坐标。

输出

每个场景输出一行，给出$Karel$从起始位置出发，访问每个蜂鸣器后再返回起始位置的最短路径长度。

输入样例 1

1  
10 10  
1 1  
4  
2 3  
5 5  
9 4  
6 5  

输出样例 1

The shortest path has length 24  

来源

Svenskt Mästerskap i Programmering/Norgesmesterskapet 2002