المسألة

لقد ضللت طريقك ودخلت قصرًا كبيرًا. يتكون هذا القصر من غرف مربعة مرتبة على شكل شبكة في الاتجاهات الشرقية-الغربية والشمالية-الجنوبية، حيث يوجد $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$ ومواضع الغرف الـ $K$ التي تحتوي على مفاتيح $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_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)$.