一共nnn个星球建立了相互连通的交通网，它们由n−1n-1n−1条边相连。
czqczqczq获得了一个动力核心，他可以选择把核心放到任意一个星球，这样所有向靠近这一星球方向移动的飞船都会加速，而背离这一星球移动的都会减速。
一共有mmm个飞船分别从aia_iai飞向bib_ibi，但飞船驾驶员并不喜欢一会儿加速而又一会儿减速。他们这么评判一条航线的无趣值：加速行驶的边的条数*减速行驶的边的条数。
现在czqczqczq想知道他把核心分别放到每个星球时，总的无趣值的大小。
第一行输入两个整数 n,mn,m n,m
接下来 n-1 行每行输入两个整数 ui,vi(1≤ui,vi≤n)u_i,v_i(1 \leq u_i,v_i \leq n)ui,vi(1≤ui,vi≤n)，表示树上的一条边。
接下来 m 行每行输入两个整数 ai,bi(1≤ai,bi≤n)a_i,b_i(1 \leq a_i,b_i \leq n)ai,bi(1≤ai,bi≤n)，表示一条航线。
nnn行，每行为czqczqczq把核心分别放到iii星球时，总的无趣值的大小。
5 2 1 2 1 3 3 4 3 5 2 5 4 5
3 1 3 2 0
1≤n,m≤3×1051 \leq n,m \leq 3 \times 10^51≤n,m≤3×105