Life of the Party

A dance party is held at the fire station in Bytetown, and everyone in town is invited. For each dance, the boys are paired with the girls so that the number of pairs formed is as large as possible. A boy and a girl may be paired only if they already know each other.

Definition. A person is a life of the party if their leaving would strictly reduce the largest number of boy-girl pairs that can be formed.

One more dance is planned, but there is a problem: the number of people currently present is exactly one over the limit set by the town fire code. One person must be chosen to leave the party and, in exchange, receives a free ticket to the next party. Everyone agrees that this person should not be a life of the party. So who exactly is a life of the party?

The first line contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 10000$, $1 \le k \le 100000$): the number of boys, the number of girls, and the number of acquaintance relations. The boys are numbered from $1$, and the girls are numbered from $1$.

Each of the next $k$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le m$), meaning that boy $a_i$ and girl $b_i$ know each other.

Output the numbers of all people who are a life of the party, one per line: first the boys, then the girls. Within each of the two groups, list the numbers in ascending order.