EuroOilTrans#3054
The North Sea region is an important oil-producing area in Europe, with annual production of million tons, transported through pipelines whose total length exceeds the Earth's equator.
The oil transportation system consists of distribution stations and pipelines. Each pipeline connects two different stations, and there is at most one pipeline between any two stations.
The efficiency of a station depends on the oil's viscosity. Therefore, the company "EuroOilTrans", which operates the pipeline network, has commissioned the development and production of new, high-precision viscosity sensors at an innovative research enterprise.
Sensor production is a complex and expensive process, so it was decided to produce only sensors (k \leq 40) to be installed at different stations. Stations must be chosen such that all pipelines are monitored: for each pipeline, at least one sensor must be installed at either endpoint of the pipeline.
Write a program to determine whether such a placement of sensors is possible and, if so, to find such a placement.
The first line contains three natural numbers: , , and (k \leq n \leq 2000, 1 \leq m \leq 10^5, 1 \leq k \leq 40). The next lines each describe one pipeline: two integers indicating the numbers of the stations it connects. Stations are numbered from to . It is guaranteed that every station is connected by at least one pipeline, and that there is at most one pipeline between any pair of stations. Numbers are separated by spaces.
On the first line, output Yes if a suitable placement of sensors exists; otherwise, output No. If a valid placement exists, output on the second line different integers — the station numbers where the sensors should be installed, in any order. If multiple valid placements exist, output any of them. Numbers on the second line must be separated by spaces.
Esempio 1