1043. 找女朋友

FS 最近天天看到朋友圈里面有人秀恩爱,寻思着也要去找个女朋友,所以尝试着去搭讪一下女生。有一个 n \times m 的地图,给你 FS 和女生的位置,FS 每一步可以向右或向下走一格,请你输出 FS 成功搭讪所需要的最少步数,若 FS 不能到达这个女生的位置,则输出 Single dog!

输入

多组数据。

第一行 T \ (1 \leq T \leq 10),表示有 T 组数据。

对于每一组数据:

第一行给出 n,m \ (1 \leq n,m \leq 100),表示地图有 nm 列;

第二行给出 x_1,y_1,表示 FS 在 x_1y_1 列;

第三行给出 x_2,y_2,表示女生在 x_2y_2 列。

行和列均从 1 开始标号,相邻两组数据间有一行空行。

数据保证输入的 (x_1,y_1)(x_2,y_2) 一定在 n \times m 的地图中。

输出

对于每一组数据,若 FS 能够到达女生的位置,输出 FS 搭讪所需要的最少步数;否则输出 Single dog!

每组数据输出后换行。

样例

标准输入 复制文本
2
3 3
1 1
2 2

5 5
1 1 
2 3 
标准输出 复制文本
2
3

来源

2018 软件学院 AK 杯程序设计竞赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 1006
通过 325