U420913 最小生成路

一个 $n$ 个点 $m$ 条边的图

给出一个 $n$ 个点 $m$ 条边的图和 $k$ 个点对 $u_i,v_i$ 现在请你求出一颗生成树 令 $far(u,v)$ 代表树上 $u$ 到 $v$ 经过的边数 求出 $\sum_{i=1}^{k} far(u_i,v_i)$ 的最小值

第一行三个数表示 $n,m,k$ 接下来 $m$ 行每行两个数 $x,y$ 表示节点 $x$ 与节点 $y$ 有一条无向边 接下来 $k$ 行每行两个数表示 $u_i,v_i$

输出 $\sum_{i=1}^{k} far(u_i,v_i)$ 的最小值

$1\le x,y,u_i,v_i \le n \le 500$ $n-1 \le m \le 50000$