Constructing a Directed Graph with Given Degrees and Forbidden Edges

You are given an integer \(n\) representing the number of nodes in a directed graph (nodes are numbered from \(1\) to \(n\)). The graph has no self-loops or multiple edges and may be disconnected. For each node, you are given its in-degree and out-degree. In addition, there are \(m\) restrictions; each restriction provides two integers \(x_i\) and \(y_i\), which mean that the directed edge \((x_i, y_i)\) does not exist in the graph.

Your task is to construct any graph that satisfies the following conditions:

• For every node \(i\), the out-degree is exactly as given.
• For every node \(i\), the in-degree is exactly as given.
• The graph does not contain any forbidden edge \((x_i,y_i)\) provided in the input.
• No self-loops (\((i,i)\)) or multiple edges are allowed.

It is guaranteed that at least one valid graph exists. If multiple answers exist, output any one.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of nodes and the number of forbidden edge restrictions).

The second line contains \(n\) integers \(d_1, d_2, \dots, d_n\) where \(d_i\) is the in-degree of node \(i\).

The third line contains \(n\) integers \(o_1, o_2, \dots, o_n\) where \(o_i\) is the out-degree of node \(i\).

Then \(m\) lines follow, each containing two integers \(x_i\) and \(y_i\) indicating that the edge \((x_i, y_i)\) is forbidden.

outputFormat

Output a valid graph in the following format:

The first line should contain an integer \(k\) equal to the total number of edges in the graph (which is \(\sum_{i=1}^{n} o_i\)).

Then output \(k\) lines, each containing two integers \(u\) and \(v\) representing a directed edge from \(u\) to \(v\).

The order of edges does not matter.

sample

3 1
1 1 1
1 1 1
1 2

3
1 3
2 1
3 2