Входной файл: input.txt Выходной файл: output.txt Время на тест: 5 секунд Тесты к задаче:Скачать
Винни-Пух и Пятачок нанялись защищать компьютерную сеть от хаккеров,
которые выкачивали из компьютеров секретную информацию. Компьютерная сеть
Винни-Пуха и Пятачка состояла из связанных между собой больших ЭВМ, к каждой
из которых подключалось несколько терминалов. Подключение к одной из больших
ЭВМ позволяло получить информацию, содержащуюся в памяти этой ЭВМ, а также всю
информацию, доступную для ЭВМ, к которым данная ЭВМ могла направлять запросы.
Хаккеры и раньше нападали на подобные компьютерные сети и их тактика была
известна. Поэтому Винни-Пух и Пятачок разработали специальную программу,
которая помогла принять меры против готовившегося нападения.
Тактика хаккеров.
При нападениях хаккеры всегда получают доступ к информации всех ЭВМ сети.
Добиваются они этого, захватывая некоторые ЭВМ сети, так чтобы от них можно
было запросить информацию у оставшихся ЭВМ. Вариантов захвата существует
множество. Например, захватить все ЭВМ. Но хаккеры всегда выбирают такой
вариант, при котором суммарное количество терминалов у захваченных ЭВМ
минимально.
Примечание.
В сети Винни-Пуха и Пяточка ни у каких 2-х ЭВМ количество терминалов не
совпадает.
Техническое задание.
Вам необходимо написать программу, входными данными которой было бы
описание сети, а выходными - список номеров ЭВМ, которые могут быть выбраны
хаккерами для захвата сети согласно их тактике.
Формат ввода.
Количество ЭВМ в сети : N
ЭВМ #1 имеет терминалов : T[1]
ЭВМ #2 имеет терминалов : T[2]
...
ЭВМ #N имеет терминалов : T[N]
Права на запрос :
A[1] B[1]
A[2] B[2]
...
A[K] B[K]
0 0
A[i] и В[i] - номера ЭВМ, последняя строка '0 0' обозначает конец списка
прав на запрос, каждая пара A[i] B[i] обозначает, что ЭВМ с номеров A[i] имеет
право запрашивать информацию у ЭВМ с номером B[i] (A[i] не равно B[i]).
При вводе числа N и T[i] - натуральные, T[i] <=1000, N<=50,
K<=2450.
Входные данные соответствуют приведенным условиям.
Формат вывода.
Номера захватываемых ЭВМ : С[1] C[2] ... С[M].
Количество захватываемых ЭВМ : <M>