FRAKTAL - konkurs programistyczny

Jasiu, nasz wybitny archeolog, eksploruje kolejną świątynię w poszukiwaniu ukrytych skarbów. Bardzo szybko znalazł miejsce, gdzie na pewno zakopano całe złoto starożytnej cywilizacji. Jest tylko mały szkopuł. Po wejściu do ogromnej komnaty Jaś przypadkowo uruchomił system bezpieczeństwa i nagle z sufitu zaczynają spadać wielkie głazy, które powoli zaczynają blokować drogę do wyjścia. Jaś musi wiedzieć po jakim czasie nie będzie w stanie wydostać się z pomieszczenia!

Komnata do której wszedł Jaś jest prostokątem o wymiarach W*K. Układ pomieszczenia można przedstawić za pomocą dwuwymiarowej tablicy o W wierszach, zawierających po K pól. Wejście (i wyjście) znajduje się na polu [W_w, W_k] (wiersz W_w, kolumna W_k). Skarb znajduje się na polu [S_w, S_k].

Jaś wie, że co minutę na jedno z pól w komnacie spadną kamienie, przez które nie da się przejść. Ostatecznie kamienie spadną na wszystkie pola w pomieszczeniu poza tymi, gdzie znajduje się wejście i skarb. Jasiowi udało się nawet ustalić w jakiej kolejności będą spadać kamienie. Przygotował listę zawierającą W*K–2 unikalnych współrzędnych określającą kolejność pól, które zostaną zablokowane w każdej kolejnej minucie. Współrzędne podane są jako wiersz i kolumna kolejno blokowanego pola.

Aktualnie Jaś znajduje się na polu ze skarbem. Powiedz po jakim czasie droga do wejścia (wyjścia) zostanie całkowicie zablokowana. Jaś może przechodzić między polami, które stykają się bokami (o ile żadne z tych pól nie jest zablokowane). Czas potrzebny na opuszczenie komnaty nie ma znaczenia.

Wejście

Na wejściu zostaną podane rozmiary komnaty W oraz K (0 < W, K ≤ 1000). Następne cztery wartości to współrzędne wejścia W_w, W_k oraz pola ze skarbem S_w, S_k (0 ≤ W_w, S_w < W, 0 ≤ W_k, S_k < K). Wejście nie musi znajdować się na obrzeżach komnaty!

W kolejnych W*K–2 liniach znajduje się lista kolejnych pól, na które spadną głazy. Każde pole opisane jest jako dwie wartości P_w i P_k (0 ≤ P_w < W, 0 ≤ P_k < K). Wszystkie podawane współrzędne znajdują się wewnątrz prostokąta opisującego komnatę.

Wyjście

Na wyjściu należy wypisać po jakim czasie droga z pola ze skarbem do wejścia (wyjścia) zostanie całkowicie zablokowana, tzn. nie będzie się dało przejść od jednego pola do drugiego zgodnie z zasadami opisanymi powyżej. Jeżeli przemieszczenie się z jednego pola do drugiego będzie możliwe zawsze, należy wypisać zawsze.

Przykład 1

3 4
0 2 2 1
2 0
1 3
1 1
0 1
1 0
0 0
0 3
2 3
1 2
2 2

9

Przykład 2

2 3
0 1 1 1
0 0
1 0
0 2
1 2

zawsze