TooDee là một vùng đất hai chiều có dạng lưới, giống hệ tọa độ Descartes. Nơi đây có những sinh vật nhỏ bé gọi là Dee, giống loài ong nhưng sống trong không gian hai chiều và rất văn minh. Tổ của Dee là những hình chữ nhật có các cạnh song song với các trục tọa độ, theo hướng đông–tây hoặc bắc–nam.

Các Dee bay trên những đường song song với các trục tọa độ, qua các điểm có tọa độ nguyên. Mọi Dee phải tuân thủ các quy tắc sau:

• Từ điểm \((x,y)\), chỉ được bay đến một trong bốn điểm kề nó: \((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\).
• Không được đi vào bên trong bất kỳ tổ Dee nào. Có thể đi trên cạnh hoặc tại đỉnh của tổ.
• Chỉ được đổi hướng bay khi đang ở trên cạnh hoặc tại đỉnh của một tổ Dee.
• Khi bắt đầu, có thể chọn hướng bay bất kỳ.

Tối nay là sinh nhật con gái của Deeficer, một viên chức của Bộ Tài sản Công cộng TooDee. Cô ấy muốn từ văn phòng về nhà nhanh nhất có thể. Với tốc độ bay một đơn vị độ dài mỗi giây, hãy tìm thời gian ngắn nhất để cô ấy về đến nhà mà vẫn tuân thủ các quy tắc trên.

Dữ liệu vào

Dòng đầu chứa số nguyên \(T\), số tình huống. Các tình huống được cho tiếp theo; trước mỗi tình huống có một dòng trống.

Dòng đầu của mỗi tình huống chứa bốn số nguyên: tọa độ \(x,y\) của văn phòng, rồi tọa độ \(x,y\) của nhà. Dòng thứ hai chứa số nguyên \(N\), số tổ Dee. Mỗi dòng trong \(N\) dòng tiếp theo chứa bốn số nguyên, là tọa độ của hai đỉnh đối diện của một tổ.

Không có hai tổ nào chồng lên nhau hoặc tiếp xúc với nhau, kể cả tại đỉnh. Văn phòng và nhà là hai điểm khác nhau. Diện tích mỗi tổ ít nhất là một đơn vị vuông.

Dữ liệu ra

Với mỗi tình huống, in trên một dòng số giây cần thiết để về nhà theo đường đi ngắn nhất. Nếu không thể về nhà mà vẫn tuân thủ các quy tắc, in chính xác No Path.

Ràng buộc

• \(1 \le T \le 20\).
• \(0 \le N \le 1000\) trong mỗi tình huống.
• Mọi tọa độ là số nguyên thuộc đoạn \([-10^9,10^9]\).

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Các điều kiện trong bảng áp dụng cho mọi tình huống của dữ liệu vào.

Ví dụ

2

1 7 7 8
2
2 5 3 8
4 10 6 7

2 1 5 4
1
3 1 4 3

9
No Path

Nguồn

APIO 2011 — Find the Path.