高桥君所在的街区可以看作一颗 $n$ 个节点的无根树，节点标号从 $1$ 到 $n$。树上每条边长度均为 $1$，定义 $\operatorname{dis}(u,v)$ 为节点 $u$ 到 $v$ 间唯一简单路径的长度。每个点可能有小吃摊，也可能没有。

接下来 $q$ 天中，第 $i$ 天高桥君打算从 $s_i$ 旅行到 $t_i$，耗时 $2\operatorname{dis}(s_i,t_i)$。因为饿肚子走路很没劲，他也可以在旅途中选择一个有小吃摊的节点 $d_i$，这样耗时变为 $2\operatorname{dis}(s_i,d_i)+\operatorname{dis}(d_i,t_i)$。

高桥君想知道每天旅行的最小耗时。

• $1\leq n,q\leq 10^5$