Автор: | Жюри всероссийской олимпиады школьников 2010 | Ограничение времени: | 2 сек | |
Входной файл: | pipeline.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | pipeline.out | |||
Максимальный балл: | 100 |
Ханты-Мансийский автономный округ — Югра является важнейшим нефтяным регионом России. Добыча нефти составляет 267 млн. т. в год, её транспортировка осуществляется по трубопроводам, общая длина которых превышает длину экватора Земли.
Система транспортировки нефти представляет собой совокупность n распределительных станций и m трубопроводов. Каждый трубопровод соединяет две различные станции. Между любыми двумя станциями проложено не более одного трубопровода.
Эффективность работы станций существенно зависит от вязкости нефти. Поэтому компания "ЮграНефтеТранс", в ведении которой находится сеть трубопроводов, заказала инновационному исследовательскому предприятию разработку и изготовление новых сверхточных датчиков вязкости на основе самых современных технологий.
Изготовление датчиков — процесс трудоёмкий и дорогостоящий, поэтому было решено изготовить k датчиков (k ≤ 40) и выбрать k различных станций, на которых датчики будут установлены. Необходимо осуществить выбор станций так, чтобы датчики контролировали все трубопроводы: для каждого трубопровода хотя бы один датчик должен быть установлен на станции, где начинается или заканчивается этот трубопровод.
Напишите программу, которая проверяет, существует ли требуемое расположение датчиков, и в случае положительного ответа находит это расположение.
В первой строке входного файла записаны три натуральных числа — n, m и k (k ≤ n ≤ 2000, 1 ≤ m ≤ 105, 1 ≤ k ≤ 40). Далее следуют m строк, каждая из которых описывает один трубопровод. Трубопровод задаётся двумя целыми числами — порядковыми номерами станций, которые он соединяет. Станции пронумерованы от 1 до n. Гарантируется, что к любой станции подведён хотя бы один трубопровод и между любыми двумя станциями проложено не более одного трубопровода. Числа в каждой строке разделены пробелами.
В первую строку выходного файла выведите слово "Yes", если требуемое расположение датчиков существует, в противном случае — слово "No". В случае положительного ответа выведите во вторую строку выходного файла k различных целых чисел — номера станций, на которых необходимо установить датчики. Номера можно выводить в любом порядке. Если существует несколько подходящих расположений датчиков, выведите любое из них. Разделяйте числа во второй строке пробелами.
№ | Входной файл (pipeline.in ) |
Выходной файл (pipeline.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|