Contest!#4803
In Berland, the annual competitive programming contest, "Berland Open," is underway. Tomorrow, there will be quarterfinals, featuring programmers, with two competitors in each quarterfinal. After the competition, an award ceremony will be held, and all winners will be invited.
However, the relationships among programmers in Berland are quite strained. Specifically, there are pairs of participants who dislike each other so intensely that if both members of any pair attend the ceremony, it will be disrupted.
Vasya is tasked with hosting the award ceremony and entertaining the programmers. He is not keen on this responsibility and secretly hopes the ceremony will be disrupted. Today, he managed to acquire the secret plan for assigning programmers to the quarterfinals. Your task is to help him determine if there is at least one way for the award ceremony to proceed without disruption.
The first line contains two non-negative integers and (0 \leq n \leq 10^5, 0 \leq m \leq 10^6). The next lines each contain two integers, representing the participants in the -th quarterfinal. The following lines each contain two integers and (1 \leq u, v \leq 2n), indicating that the -th and -th programmers are in conflict, and their joint presence at the award ceremony will cause it to be disrupted. The same pair may appear multiple times.
Programmers are numbered with natural numbers from to .
If there is at least one way for the award ceremony to be successful, print numbers: the numbers of the programmers who should attend the ceremony (if there are several possible solutions, print any of them).
If it is impossible to select winners without conflicts, print -1.
Пример 1
Пример 2