Untitled

*** De ***
Quan tuong
Xet ban co vuong kich thuoc NxN. Cac dong duoc danh so tu 1 den N, tu duoi len tren. Cac cot duoc danh so tu 1 den N tu trai qua phai.
O nam tren giao cua dong i va cot j duoc goi la o (i,j). Tren ban co co M (0<=M<=N) quan co. Voi m >0, quan co thu i o o (ri,ci), i = 1,2,...., m. Khong co 2 quan co nao o tren cung 1 o. Trong so cac o con lai cua ban co, tai o (p,q) co 1 quan tuong. Moi 1 buoc di, tu vi tri dang dung quan tuong chi co the di chuyen den duoc nhung o tren cung duong cheo voi no ma tren duong di khong phai qua cac o da co quan
Can phai dua quan tuong tu o xuat phat (p,q) ve o dich (s,t)
Cho kich thuoc ban co N, so quan co hien co tren ban co M va vi tri cua chung, o xuat phat va o dich cua quan tuong. Hay xac ding so nuoc di it nhat can thuc hien de dua quan tuong ve o dich hoac dua ra so -1 neu dieu nay khong the thuc hien duoc.

Constraints

N = 1~200

Input
Dong dau tien chua so testcase. Moi testcase cos cau truc nhu sau:
- Dong thu nhat chua 6 so nguyen N, M, p, q, s, t.
Neu M>0 thi moi dong thu i trong m dong tiep theo chua 1 cap so nguyen ri, ci xac dinh vi tri quan thu i
Hai so lien tiep tren cung 1 dong duoc ghi cach nhau it nhat 1 dau cach

Output
Voi moi testcase in ra 1 dong duy nhat laf so nuoc di tim duoc 

Sample

Input
2
5 5 5 5 5 3
1 2
1 5
2 2
4 2
4 3
8 3 7 2 1 4
5 4
3 4
4 7

Output
2
3


*** input ***
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

*** output ***
2
4
2
2
9
8
6
2
3
4
4
5
4
3
2

*** my code ***
#include<iostream>
using namespace std;

int ans;
int N, M, p, q, s, t;
int board[205][205];

int const max_queue = 1000000;
int qx[max_queue];
int qy[max_queue];
int front = -1;
int rear = -1;
bool isEmpty(){
	return front == -1;
}
void push(int x, int y){
	if (front == -1) front = 0;
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}
void pop(){
	if (front >= rear) front = rear = -1;
	else front++;
}

int dx[] = {-1, 1, 1,-1};
int dy[] = {-1, 1,-1, 1};
int visitBfs[205][205];
int bfs(int x, int y){
	front = rear = -1;
	push(x,y);
	visitBfs[x][y] = 0;
	while (!isEmpty()){
		int x1 = qx[front];
		int y1 = qy[front];
		pop();
		for (int i = 0; i < 4; i++){
			for (int k = 1; k <= 200; k++){
				int x2 = x1 + k*dx[i];
				int y2 = y1 + k*dy[i];
				if (x2>=1 && x2<=N && y2>=1 && y2<=N){
					if (board[x2][y2] == 1) break;
					if (visitBfs[x2][y2]==0 && board[x2][y2] != 1){
						push(x2,y2);
						visitBfs[x2][y2] = visitBfs[x1][y1]+1;
						if (board[x2][y2] == 2){
							return visitBfs[x2][y2];
						}
					}
				}
				
			}
		}
	}
	return -1;
}


void reset(){
	ans = 0;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			board[i][j] = 0;
			visitBfs[i][j] = 0;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; tc++){
		cin >> N >> M >> p >> q >> s >> t;
		reset();
		p = N+1-p;
		s = N+1-s;
		board[s][t] = 2;
		
		for (int i = 1; i <= M; i++){
			int r, c;
			cin >> r >> c;
			board[N+1-r][c] = 1;
		}

		ans = bfs(p,q);

		cout << ans << endl;
	}
	return 0;
}