Graph Orientation Uniqueness

Given an undirected graph with \(n\) vertices and \(m\) edges, and \(p\) restrictions of the form \((x_i,y_i)\), where in the final directed graph there must exist a directed path from \(x_i\) to \(y_i\), you are to assign a direction to each edge so that all the restrictions are satisfied. A solution is guaranteed to exist.

Your task is to determine, for each edge, whether its direction is uniquely determined across all valid orientations. If the relative order of the endpoints \(u\) and \(v\) is fixed in every valid orientation, then the edge between \(u\) and \(v\) is forced to be directed from the earlier vertex to the later vertex (i.e. \(u\to v\) if \(u\) always comes before \(v\)). Otherwise, its orientation is ambiguous.

Note: The \(p\) restrictions induce a partial order among the vertices. An edge's orientation is uniquely determined if and only if the ordering of its two endpoints is the same in every linear extension of this partial order.

inputFormat

The first line contains three integers: \(n\), \(m\), and \(p\).

The next \(m\) lines each contain two integers \(u\) and \(v\), representing an undirected edge between vertices \(u\) and \(v\).

The following \(p\) lines each contain two integers \(x_i\) and \(y_i\), representing a restriction such that the final directed graph must have a path from \(x_i\) to \(y_i\).

outputFormat

Output on the first line an integer \(k\), the number of edges whose orientation is uniquely determined.

Then output \(k\) lines, each containing two integers. For a uniquely determined edge connecting \(u\) and \(v\), if all valid orientations force it to be directed as \(u\to v\), output "u v".

sample

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

0