سرگردان در کندو

علی داشت توی جنگل‌های آمازون گردش می‌کرد. روی یکی از درخت‌ها یه کندوی عسل بزرگ دید. به سرش زد که بره توش ببینه واقعا چطوریه! این همه‌ی اون چیزیه که علی عزیز راجع به کندو فهمید:

• ساختار کندو یک شبکه از شش ضلعی‌هاست. این ساختار رادر زیر می‌بینید.
• پس از عبور از یک در که دو خانه را به هم متصل می‌کند، ماموران کندو متوجه یک فرد خارجی می‌شوند و تا ۵ واحد زمانی پس از آن مراقب آن در خواهند بود؛ لذا عبور از آن در زمان حضور نگهبان‌ها غیرممکن خواهد بود.
• بعضی از درها به دلیل اهمیت همواره نگهبان دارند.

در این‌جا برای نمونه یک شبکه‌ی $3\times 7$ را مشاهده می‌کنید. در خانه‌های همسایه‌ خانه‌ای که با عدد صفر مشخص شده، شماره‌ی حرکتی نوشته شده که پویا را از خانه‌ی صفر به آن خانه می‌برد. هر خانه با دو مختصه نشان داه می‌شود. مثلا مختصات خانه‌ی شماره‌ی ۰، $(1,1)$ و مختصات خانه‌ی شماره‌ی ۶، $(0,0)$ و مختصات خانه‌ی شماره‌ی ۱، $(0,1)$ و مختصات خانه‌ی شماره‌ی ۵، $(1,0)$ است.

علی از یکی از خانه‌ها وارد کندو شده و مسیری را طی کرده و به خانه‌های مجاور رفته است. حالا می‌خواد هرچه زودتر از اونجا بیرون بیاد، یعنی باید دوباره به خانه‌ی اولیه برگردد.

در سطر اول فایل ورودی $m$ و $n$ داده می‌شوند که نشان می‌دهند کندوی مورد بحث شبکه‌ای $m\times n$ است.

سطر دوم حاوی مختصات نقطه‌ی ورودی علی و تعداد حرکات وی در ابتدا می‌باشد. در سطر بعدی دنباله‌ی حرکات علی آمده.

سپس تعداد درهای مهم آمده و سپس مختصات خانه‌های دو سر آن‌ها.

در تنها سطر خروجی یک عدد بنویسید که تعداد حرکات لازم باشد. اگر این کار امکان‌پذیر نیست، به جای آن ۱- بنویسید.

توجه

راستی علی این‌قدر هول کرده که حضر نیست حتی برای یک واحد زمانی توی یه خونه ثابت بمونه. می‌دانیم که $1\leq m,n \leq 20$. تعداد حرکات اولیه پویا حداکثر ۳۰ تاست.

در این‌جا جهار حرکت نیاز است و دنباله‌ی جواب می‌تواند ۶، ۵، ۱ و ۲ باشد.

• سوال بعد
• سوال قبل