In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
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.
A dance party is held in a fire depot in Bytevillage and everyone in the village is invited to it. For each dance the boys are paired with the girls so that the number of pairs formed is as large as possible. A girl and a boy can form a pair only if both of them know each other.
Definition. A life of the party is such a person that if this person leaves the dance party, the maximum number of pairs of boys and girls that can be formed decreases.
Yet another dance is planned at the party, but there is a problem: the number of people currently present at the party exceeds by one the limit imposed by Bytean fire regulations. Some person has to be selected to exit the party and receive a free ticket for the next party in return. It was immediately decided that it is better not to select any person who is a life of the party. But who actually is a life of the party here?
The first line of the input contains three integers , and (, ) that represent the number of boys and girls and the number of acquaintances. The boys are numbered starting from 1, and also the girls are numbered starting from 1. The following lines contain a description of the acquaintances. Each of these lines contains two integers and (, ) that represent an acquaintance between the boy and the gal .
Your program should output the numbers of persons being a life of the party, one per line, first the boys, then the girls. Each of the two lists should be sorted in ascending order.
For the input data:
4 4 4 2 1 3 2 4 3 4 4
the correct result is:
2 3 4 1 2
Task author: Jakub Lacki.