In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Witnesses, numbered from to , have made their testimonies in a court. Each testimony is a statement of the form: “the -th witness agrees with the -th witness” or “the -th witness does not agree with the -th witness”.
If the -th witness agrees with the -th witness then he agrees also with all the witnesses that the -th witness agrees with. Similarly, the -th witness does not agree with all the witnesses that the -th witness does not agree with. We assume that every witness implicitly states: “I agree with myself”.
We say that witness is not credible if from testimonies made in a court it follows that there exists a witness such that agrees with and does not agree with .
Write a program that:
In the first line of the standard input there is a single integer , , which is the number of witnesses. In the second line there is a single integer , , which is the number of testimonies.
In each of the following lines there are two integers (, ), separated by a single space. If is positive it describes a testimony: “the -th witness agrees with the -th witness”. If is negative it means: “the -th witness does not agree with the -th witness”.
In the standard output there should be written:
For the input data:
6 12 1 3 1 6 2 -1 3 4 4 1 4 -2 4 5 5 -1 5 -3 5 2 6 5 6 4
the correct result is:
1 3 4 6
Task author: Grzegorz Jakacki.