NDD Gist - NDDCoder

Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t).

Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

Constraints

N = 1~200

Input

Dòng đầu tiên chứa số testcase. Mỗi testcase có cấu trúc như sau:

Dòng thứ nhất chứa 6 số nguyên n, m, p, q, s, t.

Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Với mỗi test case in ra 1 dòng duy nhất là số nước đi tìm được.
15
5 5 5 5 5 3
1 2
1 5
2 2
4 2
4 3
8 4 2 5 5 4
3 6
4 3
4 5
6 3
10 5 6 5 1 8
2 9
5 6
6 7
7 4
8 7
12 0 3 4 10 3
14 7 6 1 7 14
10 3
2 9
4 12
8 3
5 2
6 3
12 3
16 7 4 13 16 15
6 13
5 12
3 14
9 8
11 16
3 12
6 15
17 9 12 14 15 7
14 16
11 13
13 13
10 16
11 15
15 10
15 13
16 2
17 9
18 10 12 14 3 1
11 13
11 15
14 16
4 13
6 6
13 15
13 12
11 4
10 10
17 6
20 4 19 13 15 5
20 14
18 14
18 12
19 10
20 7 15 9 2 14
6 18
11 5
17 11
14 18
14 8
16 8
14 10
40 10 38 16 36 4
40 18
37 15
39 15
36 18
39 17
35 17
27 17
29 9
31 9
38 32
80 20 25 15 19 65
27 17
24 14
26 14
24 16
25 17
27 10
30 19
38 13
41 31
47 37
47 79
49 20
50 35
51 51
60 80
68 1
69 9
71 50
72 27
79 42
100 30 25 35 90 48
27 37
24 34
26 34
27 37
23 37
18 57
20 11
23 89
29 24
29 33
31 57
36 13
41 87
44 37
44 84
46 12
50 10
51 9
54 81
58 69
64 74
66 39
78 31
80 81
82 22
85 43
87 26
89 50
94 99
99 67
120 50 28 99 68 77
2 68
3 31
3 58
4 1
6 60
11 63
15 83
16 30
23 4
23 90
28 81
30 37
35 25
36 43
37 69
37 108
39 3
45 31
46 109
46 118
47 91
51 106
52 23
55 58
56 102
59 12
59 68
63 44
64 67
65 8
65 80
68 32
72 98
73 75
78 111
82 95
85 38
85 120
86 117
88 9
88 116
92 58
102 81
104 19
104 103
107 27
116 55
116 66
117 51
120 90
200 0 30 148 173 79
2 4 2 2 9 8 6 2 3 4 4 5 4 3 2

Title

Language

Public

View

Cancel

Font size:

Theme