Problem 3546 --道路规划

3546: 道路规划

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 3
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][216kb]

Description

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

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

Input

第一行是一个整数N(3 <= N <= 100),表示村庄的数量。接下来N,每行包含N个整数,在这N行中的第i行的第j个整数Aij表示村庄i到村庄j建立道路的费用 (1 <= Aij <= 1000)

然后有一个整数Q(0 <= Q <= N *(N + 1)/2)。接下来再Q行,每一行包含两个整数ab(1 <= < b <= N),即村庄a和b之间已经建成道路。

Output

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

Sample Input

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

Sample Output

179

HINT


题目来源:pku 2421

Source

[Submit][Status]