Se consideră harta universului ca fiind o matrice cu 250 de linii și 250 de coloane. În fiecare celulă se găsește o așa numită poartă stelară, iar în anumite celule se găsesc echipaje ale porții stelare. La o deplasare, un echipaj se poate deplasa din locul în care se află în oricare alt loc în care se găsește o a doua poartă, în cazul nostru în orice altă poziție din matrice. Nu se permite situarea simultană a mai mult de un echipaj într o celulă. La un moment dat un singur echipaj se poate deplasa de la o poartă stelară la alta.

Cerința

Dându-se un număr p (1<p<5000) de echipaje, pentru fiecare echipaj fiind precizate poziția inițială și poziția finală, determinați numărul minim de deplasări necesare pentru ca toate echipajele să ajungă din poziția inițială în cea finală.

Date de intrare

Fișierul de intrare poartas.in conține pe prima linie numărul p reprezentând numărul echipaje, iar pe următoarele p linii câte 4 numere naturale, primele două reprezentând coordonatele poziției inițiale a unui echipaj (linie coloană), următoarele două reprezentând coordonatele poziției finale a aceluiași echipaj (linie coloană).

Date de ieșire

Fișierul de ieșire poartas.out va conține un singur număr reprezentând numărul minim de deplasări necesar.

Restricții și precizări

• coordonatele pozițiilor inițiale și finale ale echipajelor sunt numere naturale din intervalul [1, 250]
• pozițiile inițiale ale celor p echipaje sunt distincte două câte două
• pozițiile finale ale celor p echipaje sunt distincte două câte două

Exemplu

poartas.in

3
1 2 3 4
6 5 3 9
3 4 1 2

poartas.out

4

Explicații

#include <bits/stdc++.h>
using namespace std;
ifstream cin("poartas.in");
ofstream cout("poartas.out");
#define MAX 251
int x[MAX][MAX], y[MAX][MAX], p, nrc;

int main()
{
    cin >> p;
    for (int i = 1, x1, y1, x2, y2; i <= p; i ++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        x[x1][y1] = x2;
        y[x1][y1] = y2;
    }
    for (int i = 0; i < MAX; i ++)
        for (int j = 0; j < MAX; j ++)
        {
            if (x[i][j])
            {
                if (x[i][j] == i && y[i][j] == j)continue;
                int i1 = x[i][j], j1 = y[i][j];
                x[i][j] = y[i][j] = 0;
                while (i1)
                {
                    if (i1 == i && j1 == j)nrc ++, i1 = 0;

                    int aui = i1, auj = j1;

                    i1 = x[aui][auj];
                    j1 = y[aui][auj];

                    x[aui][auj] = y[aui][auj] = 0;

                    nrc ++;
                }
            }
        }
    cout << nrc ;
}