Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Xét lưới ô vuông vô hạn trong đó có một số ô cấm, các ô còn lại là tự do. Các dòng và cột của lưới được đánh số theo thứ tự bởi các số nguyên … -3 -2 -1 0 1 2 3 … Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng theo thứ tự từ dưới lên trên. Ô nằm trên giao của dòng x và cột y được gọi là ô (x, y). Đặt một con xe vào ô xuất phát là một ô nào đó của lưới. Sau một bước đi, ta có thể di chuyển con xe đến một ô tự do bất kỳ nằm trên cùng một dòng hoặc cột với nó, miễn là giữa ô xuất phát và ô đích trên cùng dòng hoặc cột không có ô cấm.

Yêu cầu: Cho biết toạ độ của các ô cấm, vị trí ô xuất phát đặt con xe và vị trí ô đích nơi con xe cần đến, hãy tìm cách di chuyển con xe từ ô xuất phát đến ô đích sao cho số lượng bước đi cần thực hiện là ít nhất.

Input

Dòng đầu tiên chứa T (T ≤ 10) là số lượng test, tiếp đến là T nhóm dòng, mỗi nhóm chứa dữ liệu về một test theo khuôn dạng sau:

·        Dòng đầu tiên chứa 4 số nguyên x_s, y_s, x_t, y_t được ghi cách nhau bởi dấu cách cho biết toạ độ của ô xuất phát là (x_s, y_s) và ô đích là (x_t, y_t);

·        Dòng thứ hai chứa số nguyên dương n (n ≤ 1000) là số lượng ô cấm;

·        Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách x_i, y_i cho biết (x_i, y_i) là toạ độ của ô cấm thứ i (i = 1, 2, …, n).

Giả thiết là −10⁹ ≤ x_s, y_s, x_t, y_t ≤ 10⁹ ;  −10⁹ ≤ x_i, y_i ≤ 10⁹

Output

·        Gồm T dòng mỗi dòng chứa kết quả của một test tương ứng trong dữ liệu vào là số lượng bước đi ít nhất cần thực hiện để di chuyển con xe từ ô xuất phát đến ô đích. Ghi số −1 nếu như không thể di chuyển con xe đến ô đích. 

Example

Test 1:

Input:

1

1 –1 5 -4 

4 

1 1 

5 –5 

2 –4 

4 –1