Lyra 的暑期计划(除了陪 Evan 之外)是一个每个元素在 $[1n]$ 的序列,她计划完成一个长度为偶数的子区间的ddl,并且咕咕咕掉剩下的.
她会给区间内的ddl两两配对,两个ddl如果很接近,那么她就只需要把第一个ddl要交的作业稍作修改,在网络学堂上上传到第二个ddl.
Lyra 很聪明,所以她总是能巧妙的把区间内的ddl两两匹配使得匹配的ddl之间在树上的距离之和(唯一简单路上的边权和)最小.每个长度为偶数的区间的完成时间定义为最小配对方法中每对匹配点间距离的总和.
作为 Lyra 的朋友,你要帮她求序列每个长度为偶数的区间的ddl的完成时间之和.
第一行两个整数 $n m$ 表示树的大小和序列的长度.
注意:本题输入可能很大,建议采用较为快速的读入方式.