题目描述

有 $N$ 个村庄，编号从 $1$ 到 $N$，请你建立一些道路，使得任意两个村庄可以相连。我们说两个村 $A$ 和 $B$ 是相连的，当且仅当有一条公路在 $A$ 与 $B$ 之间，或存在一个村庄 $C$，有一条的道路连接着 $A$ 和 $C$ 之间，一条连接着 $B$ 和 $C$。

我们知道，已经有一些道路在一些村庄之间，你的工作是再建一些道路，使得所有的村庄连接并且所有的道路建造总和最低。

输入格式

第一行是一个整数 $N$，表示村庄的数量。

接下来 $N$ 行，每行包含 $N$ 个整数，在这 $N$ 行中的第 $i$ 行的第 $j$ 个整数 $A_{ij}$ 表示村庄 $i$ 到村庄 $j$ 建立道路的费用。

然后有一个整数 $Q$。接下来再 $Q$ 行，每一行包含两个整数 $a$ 和 $b$，即村庄 $a$ 和 $b$ 之间已经建成道路。

输出格式

你应该输出一行包含一个整数，表示所有村庄都连接所要建设道路的最小费用。

样例

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

179

数据范围

$3\le N\le 100$

$1\le A_{ij}\le 1000$

$0\le Q\le \frac{N(N+1)}{2}$

$1\le a<b\le N$

来源

并查集