โจทย์ปัญหา

คุณได้หลงเข้าไปในคฤหาสน์หลังใหญ่แห่งหนึ่ง คฤหาสน์หลังนี้มีโครงสร้างเป็นห้องรูปสี่เหลี่ยมจัตุรัสเรียงกันเป็นตารางตามแนวทิศตะวันออก-ตะวันตก-ใต้-เหนือ โดยมี $M$ คอลัมน์ในแนวทิศตะวันออก-ตะวันตก และมี $N$ แถวในแนวทิศเหนือ-ใต้ รวมทั้งหมด $M \times N$ ห้อง ห้องที่อยู่ในคอลัมน์ที่ $x$ นับจากทิศตะวันตก ($1 \le x \le M$) และแถวที่ $y$ นับจากทิศใต้ ($1 \le y \le N$) จะแทนด้วย $(x, y)$

ระหว่างห้อง $2$ ห้องที่อยู่ติดกันในทิศตะวันออก ตะวันตก ใต้ หรือเหนือ จะเชื่อมต่อกันด้วยประตูที่อยู่ตรงกลางผนัง ประตูแต่ละบานจะอยู่ในสถานะปิดซึ่งไม่สามารถเดินผ่านได้ หรือสถานะเปิดซึ่งสามารถเดินผ่านได้ อย่างใดอย่างหนึ่ง เมื่อประตูเปิดอยู่ การเดินทางระหว่างจุดกึ่งกลางของห้องเหล่านั้นจะใช้เวลา $1$ นาที นอกจากนี้ ที่จุดกึ่งกลางของบางห้องจะมีสวิตช์อยู่ หากกดสวิตช์ค้างไว้เป็นเวลา $1$ นาที สถานะการเปิด-ปิดของประตูทุกบานในคฤหาสน์จะสลับกันทั้งหมด

ขณะนี้ ประตูทุกบานที่เชื่อมระหว่างห้อง $2$ ห้องที่อยู่ติดกันในแนวทิศตะวันออก-ตะวันตกปิดอยู่ และประตูทุกบานที่เชื่อมระหว่างห้อง $2$ ห้องที่อยู่ติดกันในแนวทิศเหนือ-ใต้เปิดอยู่ ตอนนี้คุณอยู่ที่จุดกึ่งกลางของห้อง $(1, 1)$ และต้องการเดินทางไปยังจุดกึ่งกลางของห้อง $(M, N)$ โดยใช้เวลาน้อยที่สุด

งานของคุณ

เมื่อกำหนดขนาดของคฤหาสน์ $M, N$ และตำแหน่ง $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ ของห้องที่มีสวิตช์จำนวน $K$ ห้อง จงเขียนโปรแกรมเพื่อหาว่าต้องใช้เวลาอย่างน้อยที่สุดกี่นาทีในการเดินทางจากจุดกึ่งกลางของห้อง $(1, 1)$ ไปยังจุดกึ่งกลางของห้อง $(M, N)$ โดยเริ่มต้นจากสถานะที่ประตูทุกบานที่เชื่อมระหว่างห้อง $2$ ห้องที่อยู่ติดกันในแนวทิศตะวันออก-ตะวันตกปิดอยู่ และประตูทุกบานที่เชื่อมระหว่างห้อง $2$ ห้องที่อยู่ติดกันในแนวทิศเหนือ-ใต้เปิดอยู่ อย่างไรก็ตาม หากไม่สามารถเดินทางไปถึงห้อง $(M, N)$ ได้ ให้ระบุด้วยว่าเป็นเช่นนั้น

ข้อจำกัด

• $2 \le M \le 100000$: จำนวนห้องในแนวทิศตะวันออก-ตะวันตกของคฤหาสน์
• $2 \le N \le 100000$: จำนวนห้องในแนวทิศเหนือ-ใต้ของคฤหาสน์
• $1 \le K \le 200000$: จำนวนห้องที่มีสวิตช์
• $1 \le X_i \le M$: ตำแหน่งในแนวทิศตะวันออก-ตะวันตกของห้องที่มีสวิตช์
• $1 \le Y_i \le N$: ตำแหน่งในแนวทิศเหนือ-ใต้ของห้องที่มีสวิตช์

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• ในบรรทัดที่ $1$ มีจำนวนเต็ม $M, N, K$ คั่นด้วยช่องว่าง โดย $M$ แทนจำนวนห้องในแนวทิศตะวันออก-ตะวันตกของคฤหาสน์, $N$ แทนจำนวนห้องในแนวทิศเหนือ-ใต้ของคฤหาสน์ และ $K$ แทนจำนวนห้องที่มีสวิตช์
• ในบรรทัดที่ $i$ ($1 \le i \le K$) จาก $K$ บรรทัดถัดไป มีจำนวนเต็ม $X_i, Y_i$ คั่นด้วยช่องว่าง ซึ่งแสดงว่ามีสวิตช์อยู่ที่จุดกึ่งกลางของห้อง $(X_i, Y_i)$ ทั้งนี้ คู่ลำดับทั้ง $K$ คู่ $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ จะแตกต่างกันทั้งหมด

ข้อมูลส่งออก

พิมพ์ออกทางข้อมูลส่งออกมาตรฐานเป็นจำนวน $1$ บรรทัด ระบุจำนวนเต็มที่แทนจำนวนนาทีที่น้อยที่สุดที่ใช้ในการเดินทาง อย่างไรก็ตาม หากไม่สามารถเดินทางไปถึงห้อง $(M, N)$ ได้ ให้พิมพ์จำนวนเต็ม $-1$ แทน

เกณฑ์การให้คะแนน

• ในข้อมูลที่ใช้ตรวจให้คะแนน ร้อยละ $20\%$ ของคะแนนทั้งหมด เป็นไปตามเงื่อนไข $M \le 1000$ และ $N \le 1000$
• ในข้อมูลที่ใช้ตรวจให้คะแนน ร้อยละ $30\%$ ของคะแนนทั้งหมด เป็นไปตามเงื่อนไข $K \le 2000$
• ในข้อมูลที่ใช้ตรวจให้คะแนน ร้อยละ $50\%$ ของคะแนนทั้งหมด เป็นไปตามเงื่อนไขอย่างน้อยหนึ่งข้อจาก $2$ ข้อนี้ และไม่มีข้อมูลที่ใช้ตรวจให้คะแนนชุดใดที่เป็นไปตามเงื่อนไขทั้ง $2$ ข้อพร้อมกัน

ตัวอย่าง 1

ข้อมูลนำเข้า

3 2 1
1 2

ข้อมูลส่งออก

4

คำอธิบาย

ในตัวอย่างนี้ สามารถเดินทางจากจุดกึ่งกลางของห้อง $(1, 1)$ ไปยังจุดกึ่งกลางของห้อง $(3, 2)$ ได้ภายใน $4$ นาทีด้วยการกระทำต่อไปนี้ ซึ่งเป็นเวลาที่น้อยที่สุด:

• เดินทางไปยังจุดกึ่งกลางของห้อง $(1, 2)$
• กดสวิตช์ที่จุดกึ่งกลางของห้อง $(1, 2)$
• เดินทางไปยังจุดกึ่งกลางของห้อง $(2, 2)$
• เดินทางไปยังจุดกึ่งกลางของห้อง $(3, 2)$

ลักษณะของคฤหาสน์ในขณะนั้นแสดงดังภาพด้านล่าง ในภาพ ทิศทางด้านขวาคือทิศตะวันออก ทิศทางด้านบนคือทิศเหนือ เครื่องหมาย $\times$ แทนตำแหน่งของคุณ และเครื่องหมาย $\bigcirc$ แทนสวิตช์

ตัวอย่าง 2

ข้อมูลนำเข้า

3 2 1
2 1

ข้อมูลส่งออก

-1

คำอธิบาย

ในตัวอย่างนี้ คุณไม่สามารถเดินทางไปถึงห้อง $(3, 2)$ ได้

ตัวอย่าง 3

ข้อมูลนำเข้า

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

ข้อมูลส่งออก

25

คำอธิบาย

ในตัวอย่างนี้ ลักษณะเริ่มต้นของคฤหาสน์เป็นดังภาพด้านล่าง โปรดสังเกตว่าอาจมีสวิตช์อยู่ที่จุดกึ่งกลางของห้อง $(1, 1)$ หรือห้อง $(M, N)$ ได้เช่นกัน