Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2631
Chemfrog's Fairy Tale

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Because of the evil wizard's curse, Chemfrog became a frog. Luckily, he met Cyjj. She told him that he could become a handsome boy again if he found the pretty princess and got her kiss. But the princess was captured by the evil wizard, and she was enjailed in the XiaoYingzhou in the West Lake.

Chemfrog bought a West Lake map. He found that the West Lake was in a regular shape as the picture1 shown below. So he marked the center of the lake to be (0, 0), and the northmost point to be (0, N), the southmost point to be (0, -N), the eastmost point to be (N, 0), the westmost point to be (-N, 0). Then he could marked the position of XiaoYingzhou with P(px, py).

picture 1: suppose N is 5

Time and tide wait for no one. Chemfrog jumped into the West Lake immediately, and went forward to P. When he arrived at the position (x0, y0), he felt something strange: he could not move freely! That's because the evil wizard detected his action and bewitched the West Lake. Chemfrog realized the problem soon, and he also found the jumping rule to fight against the bewitchery:

Rule 1: jumping like the Knight in Chess.
Rule 2: jumping without falling back.
Rule 3: jumping within the West Lake.

Picture 2 and Picture 3 show the Rules:

picture 2

picture 3

Note: if chemfrog jumped to the point marked blue from the yellow point, the next jump he could choose 5 point marked green, but the black ones and the yellow one were forbidden.

So Chemfrog jumped to (x1, y1) from (x0, y0). The evil wizard would not await his doom, and he flew to the West Lake to prevent Chemfrog to meet the princess. It's supposed that Chemfrog must jump onto the XiaoYingzhou within M jumps.

Is it possible for Chemfrog to meet the princess? Now it's turn for you to calculate whether Chemfrog could meet the pretty girl successfully. If it is possible, output the minimum number of jumping.


The input will consist of several test cases. The first line of each test case is two nonnegative number, said N (2<=N<=500) and M (0<M<=500). The second line contains six integer numbers: x0, y0, x1, y1, px, py. You may know that (x0, y0), (x1, y1), (px, py) are in the West Lake, and (x0, y0) won't equal to (px, py). N=M=0 signals the end of input file.


For each case, if Chemfrog could get to the XiaoYingzhou within M jumps, output the minimun number of jumping, otherwise output -1.

Sample Input:
7 5
1 2 2 4 0 0
7 3
1 2 2 4 0 0
2 10
-1 -1 0 1 0 0
0 0

Sample Output:

Author: DENG, Wenliang
Source: ZOJ Monthly, December 2005
Submit    Status