Excursion
(Running time - 1s.)
The group of travelers has an opportunity to visit several cities.
Each traveler states two wishes on what city he/she does want or does not
want to visit. One wish expresses will to visit or not to visit exactly
one city. It is allowed that both wishes of the one traveler are the same
or that they are opposite--i.e. I want to visit city A, and I do not want
to visit city A.
Task
Your task is to write a program that:
-
reads the travelers' wishes from the input file ,
-
determines whether it is possible to form such a list of cities to be visited
(the list can be empty), that at least one wish of every traveler is satisfied,
-
writes the list of cities to be visited to the output file.
If there are several possible solutions, your program should output anyone
of them.
Input
The first line of the input file contains two positive integers n
and m ( 1<=n<=20 000, 1<=m<=8 000 ); n
is the number of travelers, and m is the number of cities. The travelers
are numbered form 1 to n, and the cities are numbered from 1 to
m. Each of the following n lines contains two nonzero integers,
separated by single space. The i+1-th line contains numbers wi
and vi representing wishes of the i-th traveler,
-m<= wi , vi <=m; wi ,
vi<>0 Positive number means that the traveler wishes
to visit that city, and negative number means that the traveler does not
wish to visit the city specified by the absolute value of the number.
Output
Your program should write one nonnegative integer l, the number
of cities to be visited, in the first line of the output file . In the
second line of the file, there should be written exactly l positive
integers in the ascending order, representing cities to be visited.
In case it is not possible to form such a list of cities, your program
should write in the first and only line the word NO.