标签存档: SGU172

SGU 172 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=172

172.eXam

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

In Russia school pupils must do some exams before leaving school. Among others, they must do two "selective" exams. This means that school provides a list of available subjects; each pupil selects two different subjects from this list and is going to do this exams. According to rules, pupil isn't allowed to do both exams at the same day, so the school must schedule the exams, i.e. provide some days when pupils will be able to do exams.

在俄罗斯学校里,小学生在离校之前必须做两个考试。这意味着学校必须提供一些可选的考试。每个学生选择两个不同的项目。根据规则每个学生不允许在同一天完成两个考试。所以学校必须安排好这些考试。

One school does not want to warn teachers too much. They want to schedule all the exams into two days in such way that exams on some subjects are on the first day, and exams on all other (and only on them) are on second. You are to write a program, which will determine, if it is possible to schedule exams in this way so that all pupils will be able to do all their selected exams.

一个学校不想让老师太辛苦,他们想在两天之内安排所有这些考试。在第一天安排一些考试,在第二天也只能在第二天安排其它的考试。你被安排写一个这样的程序来看看是否可以做到让每个学生都能参加他们的考试。

Input

On the first line of input there are two integers N and M (1<=N<=200, 1<=M<=30000) - the number of available subjects and the number of pupils. Then M lines follows; on i-th of them there are two integers - the numbers of exams, which were selected by i-th pupil. Exams are numerated from 1 to N.

在第一行有两个整数N和M,(1<=N<=200,1<=m<=30000)N代表可选择的考试的科目数,M代表学生的人数。下面的M行中分别代表一个学生选择的考试项目数。

Output

If the solution exists, write on the first line of output only one word "yes". On the second line write the total number of exams, which must be held on first day, and on the third line - the numbers of subjects of this exams. If there exist several solutions, output any. If no solution exists, write to output only one word "no".

如果安排方法存在,在第一行写"yes",在第二行输出在第一天必须安排的考试项目的数量,在第三行输出考试项目的项目数。如果存在多个安排方法,输出其中一个就可以了。如果安排方法不存在,输出"no"

继续阅读 »