「TFOI R1」Unknown Graph

题目背景

小 A 飘到了一个岛屿群里,这些岛屿都有单向桥相连接,没有两座桥连接的起始岛屿和终止岛屿都相同,更不会有桥连接一个岛屿。 但这里全是迷雾,小 A 在一个岛上只能看到这个岛与多少座桥相连。 小 A 想要知道整个岛屿群的形态,但是他并不会,所以找到了你。 如果有多种情况,你只需要告诉小 A 任意一种就行。

题目描述

有一张 $n$ 个节点的**无重边无自环的有向图**(可以不连通),每个节点的编号为 $1 \sim n$,你知道每个节点的入度和出度。 另外还有 $m$ 条限制,每条限制给定两个点 $x_{i}$ 和 $y_{i}$,表示图中不存在有向边 $(x_{i}, y_{i})$,请你求出一种满足要求的图的形态。 若有多种情况,输出任意一种即可,保证有解。

输入输出格式

输入格式


第一行一个正整数 $n$ 表示节点数量。 第二行 $n$ 个整数 $a_{i}$,表示编号为 $i$ 的节点的入度为 $a_{i}$。 第三行 $n$ 个整数 $b_{i}$,表示编号为 $i$ 的节点的出度为 $b_{i}$。 第四行一个整数 $m$,表示限制个数。 对于接下来的 $m$ 行,每行两个正整数 $x_{i}, y_{i}$ 表示一组限制。

输出格式


第一行一个正整数 $k$ 表示满足限制的图有多少条边。 接下来 $k$ 行,每行两个正整数 $u_{i}$ 和 $v_{i}$ 表示编号为 $u_{i}$ 的结点和编号为 $v_{i}$ 的结点之间有一条有向边。

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

**本题采用捆绑测试**。 - 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):无特殊限制。 对于所有数据,$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$。