P9705 "TFOI R1" Unknown Graph

Little A drifted to an archipelago. These islands are connected by one-way bridges. There are no two bridges with the same starting island and ending island, and there is also no bridge that connects an island to itself. However, everything is covered in fog. On one island, Little A can only see how many bridges are connected to this island. Little A wants to know the overall shape of the archipelago, but he cannot, so he came to you for help. If there are multiple possible cases, you only need to tell Little A any one of them.

There is a **directed graph with no multiple edges and no self-loops** (it may be disconnected) with $n$ nodes. The nodes are labeled $1 \sim n$. You know the in-degree and out-degree of each node. In addition, there are $m$ constraints. Each constraint gives two nodes $x_{i}$ and $y_{i}$, meaning that the directed edge $(x_{i}, y_{i})$ does not exist in the graph. Please find one graph structure that satisfies all requirements. If there are multiple solutions, output any one. It is guaranteed that a solution exists.

The first line contains a positive integer $n$, the number of nodes. The second line contains $n$ integers $a_{i}$, where the in-degree of node $i$ is $a_{i}$. The third line contains $n$ integers $b_{i}$, where the out-degree of node $i$ is $b_{i}$. The fourth line contains an integer $m$, the number of constraints. In the next $m$ lines, each line contains two positive integers $x_{i}, y_{i}$, representing one constraint.

The first line contains a positive integer $k$, the number of edges in a graph that satisfies the constraints. In the next $k$ lines, each line contains two positive integers $u_{i}$ and $v_{i}$, meaning there is a directed edge from node $u_{i}$ to node $v_{i}$.

**This problem uses bundled tests**. - Subtask 1 (10 points): $n \leqslant 10$. - Subtask 2 (10 points): $n = 10^3$, $a_{i} = b_{i} = 1$, $m = 0$. - Subtask 3 (20 points): $n \leqslant 100$. - Subtask 4 (60 points): no special constraints. Constraints: For all testdata, $2 \leqslant n \leqslant 10^{3}$, $0 \leqslant a_{i}, b_{i} < n$, $1\leqslant \sum{a_i} \leqslant 10^{5}$, $0 \leqslant m \leqslant 5 \times 10^4$, $1 \leqslant x_i,y_i \leqslant n$. Translated by ChatGPT 5