Critical Dance Partners

Two companies, \(L\) and \(H\), jointly organize a social evening. At the party, \(N\) employees of company \(L\) and \(M\) employees of company \(H\) wish to dance a social dance. Some employees from \(L\) and \(H\) are acquainted with each other; there are a total of \(T\) acquaintance pairs.

During the dance, each employee tries to choose one acquainted employee from the other company as a partner, and each employee may participate in at most one dance. Naturally, the more dance pairs completed the party can have, the warmer the atmosphere will be.

However, the employees are curious: for which acquainted pairs \((u, v)\) (with \(u\) from \(L\) and \(v\) from \(H\)) will forcing that pair to dance result in a reduction of the maximum number of dance pairs possible in the entire event?

Formally, let \(M\) be the size of a maximum matching in the bipartite graph defined by the two companies. For each given edge \((u,v)\), if we force that pair to dance, then we remove both employee \(u\) and employee \(v\) from the graph and compute the maximum matching of the remaining graph. Let this value be \(M_{uv}\); then the total number of pairs (including the forced pair) is \(1+M_{uv}\). We say that the pair \((u,v)\) is critical if

[ 1 + M_{uv} < M. ]

Your task is to identify all such critical pairs.

inputFormat

The first line of input contains three integers \(N\), \(M\) and \(T\) representing the number of employees in company \(L\), the number of employees in company \(H\), and the number of acquaintance pairs respectively.

Each of the following \(T\) lines contains two integers \(u\) and \(v\) (1-indexed) indicating that employee \(u\) of company \(L\) and employee \(v\) of company \(H\) know each other.

outputFormat

The first line of output should contain an integer \(K\) denoting the number of critical pairs. Each of the following \(K\) lines should contain two integers \(u\) and \(v\), representing a critical pair. The pairs should be output in the same order as they appear in the input.

sample

4 4 5
1 1
1 2
2 3
3 3
4 4

0