有n个村庄，从1到n，你应该修建一些道路，这样每两个村庄就可以互相连接。我们说两个A村和B村是相连的，只要A和B之间有一条路，或者C村有一条路，A和C之间有一条路，C和B是相连的。
我们知道有些村庄之间已经有了一些道路，您的工作是修建一些道路，以便所有村庄都能连接起来，并且所修建的所有道路的长度都是最小的。

第一行是一个整数n（3<=n<=100），即村庄数量。然后是n行，其中i-th包含n个整数，其中j-th是i村和j村之间的距离（距离应为[1000]内的整数）。然后有一个整数q（0<=q<=n*（n+1）/2）。然后是q线，每条线包含两个整数a和b（1<=a<b<=n），这意味着A村和B村之间的道路已经建成。

您应该输出一条包含整数的线路，该整数是所有要修建的道路的长度，以便所有村庄都连接起来，并且该值是最小的。

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

179

状态压缩DP