Contest!
In Berland, the annual competitive programming contest, "Berland Open," is underway. Tomorrow, there will be n quarterfinals, featuring 2n programmers, with two competitors in each quarterfinal. After the competition, an award ceremony will be held, and all n winners will be invited.
However, the relationships among programmers in Berland are quite strained. Specifically, there are m 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 n quarterfinals. Your task is to help him determine if there is at least one way for the award ceremony to proceed without disruption.
Input
The first line contains two non-negative integers n and m (0 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^6). The next n lines each contain two numbers, representing the participants in the i-th quarterfinal. The following m lines each contain two numbers u and v (1 ≤ u, v ≤ 2n), indicating that the u-th and v-th programmers are in conflict, and their joint presence at the award ceremony will cause it to be disrupted. The same pair may be mentioned multiple times.
Programmers are numbered with natural numbers from 1 to 2n.
Output
If there is at least one way for the award ceremony to be successful, print n numbers - the numbers of the programmers who should attend the ceremony (if multiple successful configurations exist, print any one of them).
If it is impossible to select winners without conflicts, print the number -1.