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