Problem description
Nareszcie, piątek po lekcjach, nadszedł czas na zasłużoną grę w Kopalniane rzemiosło. Jak to zawsze bywa, od razu po wejściu na serwer odezwał się do Ciebie Jasio, który opowiedział Ci, co zbudował na waszym wspólnym serwerze.
Nowa wioska Jasia składa się z N wysp, z których każda para była połączona kładką. Na każdej z nich miał swój dom dokładnie jeden wieśniak. Ich ruchy były bardzo charakterystyczne, a polegały one na tym, że w kolejnych momentach dwóch wieśniaków zamieniało się wyspami, używając do tego łączącej je kładki. W ten sposób, w każdym momencie, na jednej wyspie znajdował się dokładnie jeden wieśniak. Dodatkowo wszystkie akcje wykonywali oni w taki sposób, że każdego dnia wieczorem każdy z nich znajdował się w swoim własnym domu.
Niestety, gdy tylko Jasio zaczął prezentować Ci swoje nowe dzieło, okazało się, że Staś grający na tym samym serwerze zrobił mu złośliwy żart. Staś podłożył na wszystkich kładkach ładunki wybuchowe, które sprawiały, że po każdej akcji wieśniaków (polegającej na ich zamianie miejscami) kładka ta wybuchała i nie dało się przez nią więcej przejść.
Na razie udało wam się znaleźć logi serwera, z których dało się wyczytać kolejne ruchy wieśniaków. Dodatkowo, udało wam się spostrzec, że dwóch wieśniaków dotychczas nie wykonało żadnej akcji, czyli mają oni dostępne wszystkie kładki wychodzące z ich wysp. Czy za pomocą tych informacji jesteś w stanie powiedzieć, czy istnieje jeszcze jakakolwiek szansa, że wieśniacy wykonując dalej akcje tego samego typu co wcześniej, wrócą na swoje pierwotne wyspy? Pamiętaj, że pozostałe kładki cały czas są zaminowane i przejście po nich ciągle prowadzi do ich destrukcji.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę wysp, a zarazem wieśniaków, w wiosce Jasia.
W drugim wierszu wejścia podane jest N liczb całkowitych a1, a2, …, aN oddzielonych pojedynczymi spacjami – i-ta z nich oznacza numer wyspy na którą chce powrócić wieśniak, który znalazł się po wykonanych aktualnie ruchach na i-tej wyspie.
W trzecim wierszu wejścia znajduje się pojedyncza liczba całkowita M – liczba dotychczas wykonanych przez wieśniaków ruchów.
W kolejnych M wierszach wejścia znajdują się pary liczb lj, rj, oznaczające że w j-tym ruchu zamieniali się ze sobą wieśniacy będący aktualnie na wyspach o numerach lj oraz rj. Oznacza to w szczególności, że kładka pomiędzy tymi wyspami już nie istnieje.
Możesz uznać, że dane są poprawne, tj. dotychczasowe pary się nie powtarzają, dwóch wieśniaków dotychczas nie wykonało żadnego ruchu, a końcowe wykonie wszystkich ruchów z wejścia skutkuje w ustawieniu podanym w drugim wierszu wejścia.
Wyjście
Na wyjściu wypisz liczbę − 1, jeżeli nie istnieje ciąg zamian nie dłuższy niż 1 000 000, który doprowadziłby wszystkich wieśniaków do swoich domów.
W przeciwnym przypadku wypisz liczbę K nie większą niż 1 000 000, a następnie K wierszy zawierających pary liczb vi, wi oddzielonych spacją, oznaczających że w i-tym ruchu wieśniacy znajdujący się na wyspach vi i wi powinni zamienić się miejscami. Wszystkie kładki których użyjesz muszą być dotychczas nieużyte, a każdej z nich możesz użyć tylko raz. Jeżeli istnieje wiele poprawnych rozwiązań, możesz wypisać dowolne z nich.
Ograniczenia
2 ≤ N ≤ 10 000, 0 ≤ M ≤ 10 000.
Dla dowolnych i, j (i≠j) zachodzi 1 ≤ ai ≤ N, ai ≠ aj, 1 ≤ lj, rj ≤ N, lj ≠ rj.
Przykłady
| Wejście | Wyjście | |
|
|