Wieże

Limit pamięci: 32 MB

Na szachownicy ustawiamy wież, gdzie . Ustawienie wież musi spełniać następujące warunki:

• Dla każdego , -tą wieżę wolno postawić tylko w prostokącie określonym przez dwie pary współrzędnych: , , gdzie to współrzędne pola w lewym górnym rogu prostokąta (wiersz, kolumna), zaś to współrzędne pola w prawym dolnym rogu, oraz . Pole w lewym górnym rogu szachownicy ma współrzędne , zaś pole w prawym dolnym rogu ma współrzędne .
• Żadne dwie wieże nie mogą się atakować, to znaczy nie mogą stać w tym samym wierszu lub tej samej kolumnie.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia rozmiar szachownicy oraz dla każdego współrzędne prostokąta, w którym wolno postawić -tą wieżę,
• bada, czy można ustawić wieże, każdą w ustalonym dla niej prostokącie, tak aby żadne dwie nie atakowały się wzajemnie i jeśli tak, znajduje jedno takie ustawienie,
• zapisuje na standardowe wyjście jedno ustawienie wież spełniające warunki zadania albo jedno słowo NIE, jeśli takie ustawienie nie istnieje.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia , . W każdym z następnych wierszy są zapisane cztery liczby całkowite dodatnie nie większe niż oddzielone pojedynczym odstępem. Liczby w -tym z tych wierszy są współrzędnymi prostokąta, w którym wolno postawić -tą wieżę.

Wyjście

Na standardowe wyjście należy zapisać: jedno słowo NIE, albo w każdym z kolejnych wierszy dwie liczby całkowite oddzielone pojedynczym odstępem. Liczby w -tym wierszu powinny określać ustawienie -tej wieży (wiersz, kolumna); ta wieża powinna leżeć w prostokącie, którego współrzędne podano w -szym wierszu wejścia. Zwróć uwagę, że pozycje wież powinny być wypisane w takiej kolejności, w jakiej zostały wczytane współrzędne prostokątów, w których te wieże mogą się znaleźć.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

1 1
2 3
3 2
4 4

Autor zadania: Krzysztof Diks.