Sparing w Programowaniu Zespołowym Politechnika Poznańska, 16.04.2004

Opis

Mamy za zadanie sprawdzić efektywność sieci zarządzającej rozdzielaniem cieczy. Sieć składa się z n wejść i m wyjść. Wejścia są ponumerowane 1 . . . n, a wyjścia 1 . . . m. Wejścia i wyjścia są połączone rurami. Jednak cała sieć jest budowana w bardzo specyficzny sposób. Najpierw wybiera się rurę główną, o pewnej wytrzymałości w > 0. Następnie wybiera się wejście i (1 ≤ i ≤ n) i wyjście j (1 ≤ j ≤ m), jakie chce się połączyć i łączy się je rurą główną. Następnie łączy się wejścia o numerach i + 1, i + 2, . . ., min{n, i + w - 1} z wyjściem j rurami pobocznymi o wytrzymałościach w - 1, w - 2, . . ., max{1,w - n + i}. Jeżeli w = 1 to łączymy tylko wejście i i wyjście j rurą główną. Do sieci można dołożyć wiele rur głównych, ale każde wyjście może być połączone co najwyżej jedną taką rurą. Ciecz jest przesyłana od wejść do wyjść.

Pojawia się jednak pewien problem - ciecze nie mogą się mieszać, więc do każdego wyjścia możemy przesyłać ciecz tylko przez jedną rurę z nią sąsiadującą. Także wejścia mają pewne ograniczenie - nie możemy wysyłać z jednego wejścia cieczy przez więcej niż jedną rurę, gdyż będzie się to wiązało z niepożądanym spadkiem ciśnienia. Musimy znaleźć taki układ przewodów wykorzystywanych do przesyłania cieczy, żeby liczba wyjść, do których dochodzi ciecz była jak największa.

Uwaga!!! Ze względu na mase wykonywanej pracy, masz dostęp do maszyny z 64MB na sterte oraz 64MB na stos.

Specyfikacja wejścia

W pierwszym wierszu znajdują się dwie liczby naturalne n (1 ≤ n ≤ 10^6) oraz m (1 ≤ m ≤ 10^6)(opisane w treści zadania). W kolejnych m wierszach znajdują się opisy połączeń. Jeżeli w i + 1 wierszu znajdzie się zero, to oznacza, że i-te wyjście nie jest połączone rurą główną. Jeżeli znajdzie się tam dodatnia liczba całkowita w(1 ≤ w ≤ 10^6), to oznacza, że wyjście o numerze i jest połączone rurą główną o wytrzymałości w. W tym przypadku w i + 1 wierszu znajdzie się jeszcze jedna liczba całkowita - x, oznaczająca numer wejścia połączonego daną rurą głównym. Wyjście i jest połączone rurami pobocznymi zgodnie z opisem konstrukcji sieci.

Specyfikacja wyjścia

W pierwszym wierszu należy wypisać jedna liczbę całkowitą l równą maksymalnej liczbie działających wyjść. W następnych l wierszach należy wypisać po dwie liczby x i y oznaczające, że wykorzystuje się rurę pomiędzy wejściem x a wyjściem y. Jeżeli istnieje wiele możliwości, podaj dowolną z nich. Ciąg indeksów wejść musi być ciągiem rosnącym.

Przykład

9 6
3 4
3 1
5 2
0
5 4
4 8

5
1 2
2 3
4 1
5 5
8 6

Po prawej stronie znajdują się wejścia, a po lewej wyjścia. Linie kreskowane oznaczają rury poboczne, linie ciągłe rury główne. Połączenia pogrubione są wykorzystaniem rur zgodnym z przykładowym wyśjściem.