İt, xain və kabel#11079
İndi xəyanətkarın iti var! Kosmik gəminin göyərtəsi n \cdot m ölçülü bir dama taxtası kimi təsvir edilir, burada sətirlər yuxarıdan aşağıya -dən -ə, sütunlar isə soldan sağa -dən -ə qədər nömrələnmişdir. Bəzi qonşu hüceyrələr arasında kabel seqmentləri yerləşdirilib.
Oyunun əvvəlində it hüceyrəsində, yəni sol üst küncdə yerləşir. O, oyunçulardan birini seçir, deyək ki, seçilmiş oyunçu hüceyrəsindədir. İt başlanğıc mövqeyindən hüceyrəsinə qədər olan ən qısa marşrutlardan birini seçir (bir gedişdə it qonşu hüceyrəyə keçə bilər). Bundan sonra, it və oyunçu növbə ilə gedişlər edirlər. İt əvvəlcədən seçilmiş marşrut üzrə qaçır, oyunçu isə həmin marşrutun sonundan ona doğru qaçır. İlk gedişi it edir. Bu proses it və oyunçu eyni hüceyrədə olana qədər davam edir. Hər dəfə it kabel seqmentindən keçəndə, onu dişləyir.
Oyunçulara kömək edin, it maksimum neçə kabel seqmentini dişləyə bilər.
Birinci sətirdə üç tam ədəd , və k\:(1 \le n, m \le 200000, n \cdot m \le 200000, 0 \le k \le n \cdot (m - 1) + (n - 1) \cdot m) — sahənin ölçüləri və kabel seqmentlərinin sayı verilir.
Sonra kabel seqmentlərinin təsviri verilir. Hər bir seqment dörd tam ədəd x_1, y_1, x_2 və y_2\:(1 \le x_1, x_2 \le n, 1 \le y_1, y_2 \le m) ilə təsvir edilir. Bu ədədlər iki qonşu hüceyrənin (x_1, y_1) və (x_2, y_2) mövqelərini göstərir, onların arasında kabel seqmenti yerləşir. Qonşu hüceyrələrin yan-yana olduğu təmin edilir.
Növbəti sətirdə bir tam ədəd q\:(1 \le q \le 20) — oyunçuların mövqeləri üçün cavabın hesablanmalı olduğu hallar sayı verilir.
Sonrakı sətirdə hər biri iki tam ədəd və y\:(1 \le x \le n, 1 \le y \le m) — oyunçunun mövqeyi verilir.
sətir çıxarın. -ci sətirdə -ci halda it tərəfindən dişlənə biləcək maksimum kabel seqmentlərinin sayını verin.
Aşağıda birinci və ikinci testlərdə kabellərin yerləşməsi göstərilmişdir.
Nümunə 1
Nümunə 2