Problem description

Kr4sn4l to groźny wirus komputerowy, który odtwarza na zapętleniu utwór My jesteśmy krasnoludki, a w dzień Barbórki wyświetla użytkownikowi pewien graf dwudzielny¹ i mówi:

Jeśli użytkownik nie spełni żądania (nie znajdzie w grafie cyklu długości 4), to Kr4sn4l formatuje mu dysk ce.

Grafy wyświetlane przez Kr4sn4la są dość duże: mogą mieć po kilkaset tysięcy wierzchołków, więc zadanie nie jest trywialne. Wirus ma jednak pewną podatność: z dwóch zbiorów niezależnych², na które dzielą się wierzchołki tych grafów dwudzielnych, jeden ma zawsze nie więcej niż 3000 wierzchołków.

Zdarza się też, że w wyświetlonym grafie nie ma odpowiedniego cyklu. W takim wypadku nic już nie da się zrobić: Kr4sn4la nie da się usunąć, bo zmienia gwarę systemu na ślōnsko godke.

Tak się składa, że nadszedł dzień Barbórki, a na Twoim ekranie wyświetlił się graf dwudzielny. Znajdź w nim dowolny cykl długości 4 lub stwierdź, że taki cykl nie istnieje.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne: S, T i M. Graf wyświetlony przez Kr4sn4la ma dokładnie S + T wierzchołków i M krawędzi.

W i-tym z kolejnych M wierszy wejścia znajdują się dwie liczby całkowite U_i i V_i, oznaczające, że istnieje krawędź pomiędzy wierzchołkami o numerach U_i i V_i.

Wyjście

W jedynym wierszu wyjścia powinny znaleźć się cztery liczby całkowite, będące numerami wierzchołków cyklu długości 4 w dowolnej kolejności. Jeśli w danym grafie nie istnieje cykl długości 4, to zamiast tego w jedynym wierszu wyjścia powinna znaleźć się liczba -1.

Ograniczenia

2 ≤ S ≤ 300 000,

2 ≤ T ≤ 3000,

4 ≤ M ≤ min (S⋅T,300 000),

1 ≤ U_i ≤ S,

S + 1 ≤ V_i ≤ S + T,

(U_i,V_i) ≠ (U_j,V_j) dla i ≠ j.

Gwarantowane jest, że pomiędzy żadnymi dwoma wierzchołkami o numerach 1, …, S, ani żadnymi dwoma wierzchołkami o numerach S + 1, …, S + T nie ma krawędzi.

Przykłady

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

1 2 4 5

3 2 4
1 4
1 5
2 5
3 5

-1

4 4 10
1 7
3 6
1 8
4 5
2 6
4 7
1 6
2 8
3 5
3 7

1 2 6 8