Life of the Party

Problem Source

ONTAK 2010

Problem Description

There are $n$ boys and $m$ girls at a dance party. A boy and a girl can form a dancing pair if and only if they know each other.

We call a person the "life" of this party if and only if, should they not attend the party, the maximum number of simultaneous dancing pairs would drop.

Given the acquaintance relationships between boys and girls, you need to output the indices of the boys and the girls who are the "life" of this party.

Input Format

The first line contains three integers $n, m, k(1\leq n,m \leq 10^4, 1\leq k\leq 10^5)$, representing $n$ boys, $m$ girls, and $k$ relationships.

The following $k$ lines each contain two integers $a_i, b_i(1\leq a_i\leq n, 1\leq b_i\leq m)$, meaning boy $a_i$ and girl $b_i$ know each other.

Output Format

First output the indices of the boys who are the "life" of the party, one per line, in ascending order; then output the indices of the girls, also one per line, in ascending order.

Sample Input

4 4 4
2 1
3 2
4 3
4 4

Sample Output

2
3
4
1
2

Constraints

$1\leq n,m \leq 10^4$, $1\leq k\leq 10^5$.

Hint

• Compute a maximum bipartite matching and the Dulmage-Mendelsohn decomposition. A vertex is "critical" (the life of the party) exactly when it is not in the set of vertices that can be matched in every maximum matching — i.e. it belongs to the "unmatched-side" or "inessential" part of the decomposition.