W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Bajtocka Agencja Informacyjna (BAI) posiada n komputerów zorganizowanych w sieć. Komputery są ponumerowane liczbami od 1 do , a komputer o numerze 1 jest serwerem. Komputery są połączone za pomocą jednokierunkowych kanałów informacyjnych, które łączą pary komputerów. Cała sieć jest skonstruowana tak, że z serwera można przesłać - bezpośrednio lub pośrednio - informacje do każdego innego komputera.
Gdy BAI zdobywa nową wiadomość, to zostaje ona umieszczona na serwerze, a następnie rozpropagowana w sieci. Szef agencji zastanawia się, co stałoby się w przypadku, gdyby jeden z komputerów przestał zupełnie działać, np. wyleciał w powietrze w wyniku ataku terrorystycznego. Wówczas mogłoby się okazać, że nowo zdobyte informacje nie docierałyby do któregoś z pozostałych komputerów, gdyż uszkodzony komputer był pośrednikiem nie do uniknięcia. Komputery, których awaria mogłaby doprowadzić do takiej sytuacji, nazwiemy komputerami krytycznymi. Na przykład w sytuacji przedstawionej na poniższym rysunku komputerami krytycznymi są komputery o numerach 1 i 2 - 1 jest serwerem, natomiast każda informacja przesyłana z serwera do komputera 3 musi przejść przez komputer 2.
Napisz program, który:
W pierwszym wierszu wierszu znajdują się dwie liczby całkowite, i , oddzielone pojedynczym znakiem odstępu. Liczba to liczba komputerów w sieci, , a to liczba kanałów informacyjnych, . Każdy z kolejnych wierszy opisuje pojedynczy kanał informacyjny i składa się z dwóch liczb całkowitych oddzielonych pojedynczym odstępem. Są to odpowiednio i ( i ), co oznacza, że kanał przesyła informacje z komputera o numerze do komputera o numerze . Możesz założyć, że nie ma dwóch kanałów informacyjnych, które zaczynają się i kończą w tych samych punktach.
Wyjście powinno się składać z dwóch wierszy. W pierwszym wierszu powinna znaleźć się jedna liczba - liczba komputerów krytycznych. W drugim powinny znaleźć się numery komputerów krytycznych pooddzielane pojedynczymi odstępami, wymienione w kolejności rosnącej.
Dla danych wejściowych:
4 5 1 2 1 4 2 3 3 4 4 2
poprawną odpowiedzią jest:
2 1 2
Autor zadania: Krzysztof Onak.