题目描述

有 $N$ 个村庄，编号为 $1$ 到 $N$，你需要修建一些道路，使得任意两个村庄之间都能互相连通。

我们定义两个村庄 $A$ 和 $B$ 是连通的，当且仅当：

$A$ 与 $B$ 之间直接有一条道路，或

存在一个村庄 $C$，使得 $A$ 与 $C$ 有道路连接，且 $C$ 与 $B$ 连通。

我们已经知道某些村庄之间已经存在道路。你的任务是修建一些新的道路，使得所有村庄都互相连通，同时新建道路的总长度最小。

输入格式

第一行是一个整数 $N$（$3 \leq N \leq 100$），表示村庄数。

接下来 $N$ 行是一个 $N \times N$ 的邻接矩阵，第 $i$ 行第 $j$ 列的值表示村庄 $i$ 和村庄 $j$ 之间的距离 $d_{ij}$，其中 $1 \leq d_{ij} \leq 1000$。

然后是一个整数 $Q$（$0 \leq Q \leq \frac{N(N+1)}{2}$），表示已经存在的道路数量。

接下来 $Q$ 行，每行两个整数 $a$ 和 $b$（$1 \leq a < b \leq N$），表示村庄 $a$ 和 $b$ 之间已经修建了道路。

输出格式

输出一个整数，表示新建的道路总长度，使得所有村庄连通且代价最小。

3
0 990 692
990 0 179
692 179 0
1
1 2

179