题目描述
在奇怪国的道路规划中，共有 个城市，通过 条双向道路相连，其中第 条道路连接第 和第 个城市。两个城市之间至多存在一条直接连接的道路，并且任意两个城市之间都能通过这些道路互相到达。聪明的你一眼就看出：满足所有这些条件的规划，一定是由恰好一条环线和若干条（也可能没有）与环线相连的支线组成。
为了满足以上条件进行规划，Karl 国王依次选择了 个城市 ，并修建 条道路构建一条环线 。接着修建 条道路构建其他城市的支线并连接到环线上，其中第 条道路连接第 和第 个城市。
在公布方案后，有一些选择恐惧症患者提出意见：有时从起点到目的地会存在两条不同的路径！他们希望对道路规划进行修改，使得任意两个城市之间有且仅有一条不绕路的方式抵达。聪明的你又一眼看出：只需要在环线上任意拆除一条道路，就可以完成任务！
然而，Karl 国王不希望他们的提议顺利通过，于是他提出了一个条件：在拆除道路后，必须在环线上选择一个城市，定为首都。
既然是首都，那就要让各地的居民前往首都的时间越短越好。Karl 国王告诉你，在第 个城市中有着 名居民。而他希望所有居民从居住地前往首都时，经过的总道路数最小。特别地，首都居民前往首都时经过的道路数为 。
请聪明的你来决定需要删除的道路和以及首都的位置，满足 Karl 国王的要求。你只需要输出在你找到的最优方案中，所有居民从居住地前往首都时经过的总道路数。
输入格式
从标准输入读入数据。
第一行两个正整数 和 。
第二行 个正整数 。
随后 行，第 行两个正整数 和 。
最后一行 个正整数 。
输出格式
输出到标准输出。
输出一行一个整数表示答案。
样例1输入
6 3
2 5 4
3 2
1 4
2 6
2 2 1 1 4 3
样例1输出
样例1解释
| 拆除道路 |
首都位置 |
所有居民前往首都的总道路数 |
|
|
16 |
|
22 |
|
15 |
|
|
17 |
|
16 |
|
21 |
|
|
13 |
|
20 |
|
18 |
最优方案为拆除第 和第 个城市之间的道路，并将首都设在 号城市处。
样例2输入
11 6
6 9 5 10 3 8
8 2
6 4
7 2
1 9
3 11
83 287 111 179 13 38 366 17 41 25 98
样例2输出
样例3
见题目目录下的 3.in 与 3.ans。
该样例满足特殊性质 A。
样例4
见题目目录下的 4.in 与 4.ans。
该样例满足特殊性质 B。
样例5
见题目目录下的 5.in 与 5.ans。
该样例满足特殊性质 C。
样例6
见题目目录下的 6.in 与 6.ans。
子任务
对于全部的测试数据，保证 ，。
保证所有的 互不相同。
保证两个城市之间至多存在一条直接连接的道路，并且任意两个城市之间都能通过这些道路互相到达。
| 测试点 |
|
|
特殊性质 |
|
\leq 200 |
\leq 1,000 |
|
|
\leq 2,000 |
|
\leq 2 \times 10^5 |
\leq 10^6 |
A |
|
B |
|
C |
|
|
- 特殊性质 A：。
- 特殊性质 B：。
- 特殊性质 C：。