Tartaki

Limit pamięci: 32 MB

We wsi Bajtowo wszystkie gospodarstwa są położone po jednej stronie bardzo długiej drogi, gdyż po jej drugiej stronie znajduje się Bajtocki Park Narodowy i tam gospodarstw budować nie wolno. Wójt wsi postanowił wpłynąć pozytywnie na jej rozwój (a co za tym idzie na zawartość swojego portfela) i przekształcić ją w potentata branży meblowej. Dlatego też wybudowano tyle samo tartaków co gospodarstw we wsi, wszystkie oczywiście przy jedynej we wsi drodze. Wójt postanowił, że każdy tartak będzie dostarczał drewno jednemu, ściśle dla niego określonemu gospodarstwu, które będzie produkować z tego drewna meble.

Wójt natrafił jednak na problem natury logistycznej - brakowało możliwości transportu drewna, gdyż jedyna wiejska droga była zbyt ruchliwa i niebezpieczna. Dlatego też postanowił wybudować drogi, które będą łączyły tartaki z gospodarstwami (jeden tartak ma być połaczony z jednym gospodarstwem). Drogi te ze względów bezpieczeństwa nie mogą się przecinać; ponadto mogą one przebiegać wyłącznie po jednej stronie głównej wiejskiej drogi, nie mogą wkraczać na teren parku narodowego.

Ponieważ wójt ma problemy z takim połączeniem tartaków z gospodarstwami w pary, aby dało się żądany układ dróg wytyczyć, poszukuje informatyka, który mu w tym pomoże (a już wkrótce będzie go mógł sowicie wynagrodzić!). Czy skusisz się i pomożesz wójtowi?

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia położenia tartaków i gospodarstw przy drodze,
• wyznaczy pewne przyporządkowanie tartaków gospodarstwom, w którym da się poprowadzić żądany układ dróg,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę gospodarstw we wsi. Drugi wiersz zawiera jeden napis o długości , złożony wyłącznie z liter g i t, oznaczający układ gospodarstw i tartaków przy drodze. Droga biegnie w kierunku wschód-zachód, układ gospodarstw i tartaków podany jest w kierunku z zachodu na wschód, a park położony jest na południe od drogi (patrz też rysunek przykładowy).

Wyjście

Jeśli szukane przyporządkowanie nie istnieje, Twój program powinien wypisać na standardowe wyjście jedno słowo . W przeciwnym razie powinien wypisać wierszy. Każdy z nich powinien zawierać parę liczb całkowitych, oddzielonych pojedynczym odstępem i oznaczających numer gospodarstwa i numer tartaku, które powinny być połączone drogą. Gospodarstwa numerujemy w kierunku z zachodu na wschód liczbami od do (tartaki podobnie; gospodarstwa i tartaki mają oddzielną numerację). Jeżeli istnieje więcej niż jedno poprawne przyporządkowanie, Twój program powinien wypisać dowolne z nich.

Przykład

3
gtggtt

2 1
1 3
3 2

Przykładowe połączenie gospodarstw (czarne kółka) i tartaków (białe kółka) drogami.

Uwaga: Istnienie ,,odstępów'' między gospodarstwami i tartakami a główną drogą służy tylko lepszemu zilustrowaniu sytuacji - w rzeczywistości gospodarstwa i tartaki leżą tuż przy drodze i nie można prowadzić drogi między którymkolwiek gospodarstwem czy tartakiem a główną drogą.

Autor zadania: Jakub Radoszewski.