Enunț
Zoli joacă cu un labirint de dimensiune N x N
, format din camere de dimensiune 1 x 1
, inițial toate inaccesibile. Auzind că Zoli este mare informatician, Dănutz și D’Umbră au decis să îl pună la încercare, după cum urmează:
1 x y
: Dănutz transformă camera inaccesibilă (x, y)
într-una accesibilă.
2 x1 y1 x2 y2
: D’Umbră îl întreabă pe Zoli care este numărul minim de camere ce trebuie traversate pentru a ajunge din camera accesibilă (x1, y1)
în camera accesibilă (x2, y2)
.
Cerința
Zoli a rezolvat deja această problemă, fiind una banală. El s-a dus să se joace LOL și este curios dacă o poți rezolva și tu. Pentru M
evenimente de forma celor de mai sus, să se scrie un program care le procesează și afișează în fișierul de ieșire rezultatele operațiilor de tip 2
, în ordinea în care acestea apar în fișierul de intrare.
Date de intrare
Fișierul de intrare episodul3.in
conține pe prima linie numerele N
și M
, iar pe următoarele M
linii cele M
operații.
Date de ieșire
Fișierul de ieșire episodul3.out
va conține pe fiecare linie rezultatele operațiilor de tipul 2
, în ordinea în care acestea apar în fișierul de intrare.
Restricții și precizări
1 ≤ N ≤ 1000
1 ≤ M ≤ 250.000
1 ≤ x, y ≤ N
- pentru operațiile de tipul
1
: camera(x, y)
va avea exact o cameră vecină pe linie sau coloană deja accesibilă la momentul transformării sale, excepție făcând camera care este transformată prima. - InParser
- OutParser
Exemplu:
episodul3.in
5 7 1 1 1 1 1 2 2 1 1 1 2 1 2 2 1 1 3 2 1 3 2 2 2 1 1 2 2
episodul3.out
2 3 3