当前没有测试数据。

题目描述

有 $n$ 个村庄，编号 $1\sim n$，你需要修建一些道路，使得每两个村庄都可以相连。我们称村庄 $A,B$ 相连，当且仅当 $A,B$ 之间有一条道路，或者存在一个村庄 $C$，使得 $A,C$ 之间有一条道路，并且 $C,B$ 相连。

我们已经知道一些村庄之间已经有了一些道路，你的任务是修建一些道路，使得所有村庄都能相连，并且所修建的道路总长度最小。

输入

第一行是一个整数 $n(3 \leq n\leq 100)$，表示村庄的数量。

接下来是 $n$ 行，第 $i$ 行包含 $n$ 个整数，其中第 $j$ 个整数表示村庄 $i,j$ 之间的距离 $x(1\leq x \leq 10^3)$。

然后是一个整数 $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

Constructing Roads HDU - 1102