比较唐的是，昨天口题的时候没看到强制在线这个性质，这下这下了。

虽然其实有强制在线也不难。

思路

注意到存在强制在线，所以任意一次询问的时候我们需要直接在并查集上找到对应的答案。

这启发我们把第几次连边的信息直接放在这条边上，变成这条边的边权。那么查询的时候只需要求这两个点路径最大值即可。

但是我们需要保留从属关系，所以不能路径压缩，但是不做优化直接求 LCA 会时间会炸。考虑直接按 dep 合并，dep 小的作为 dep 大的树的子树，易证明这样树高就是 $O(\log n)$ 量级的，暴力往上跳就好了。