题目说明

有N个村庄，从1到N编号，你应该修建一些道路，这样每两个村庄就可以相互连接。我们说两个村庄A和B是相连的，当且仅当A和B之间有一条道路，或者存在一个村庄C，使得A和C之间有道路，并且C和B是连接的。

我们知道，一些村庄之间已经有一些道路，你的工作是修建一些道路，以便所有村庄都能连接起来，并且所有修建的道路的长度都是最小的。

输入格式

第一行是一个整数N（3<=N<=100），代表村庄的数量。然后是N行，其中第i行包含N个整数，这N个整数中的第j行是村庄i和村庄j之间的距离（距离应该是[1，1000]内的整数）。

然后有一个整数Q（0<=Q<=N*（N+1）/2），表示已建成道路的数量。然后是Q行，每行包含两个整数a和b（1<=a<b<=N），表示村庄a和村庄b之间的道路已经建成。

输出格式

输出需要构建的所有道路的最小长度。

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

179