P3995 树链剖分

树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。(摘自百度百科)

大宁最近在研究树链剖分。他发现树链剖分的时间复杂度主要由轻重链的划分方式保证，最常见的剖分方式是按照子树大小剖分。如图（摘自百度百科），黑边为重链，长度任意，白边为轻链，长度全部为 $1$。注意，下图 1-2、1-3 为不同轻链。  其中对于每个节点，其在重链上的儿子叫做重儿子，且只有唯一一个，而叶子节点没有重儿子。例如对于图上 1 号点，重儿子是 $4$ 号点。显然，对于不同剖分方式，同一组查询访问的链的数量不同。现在给定一棵根为 1 号节点的有根树和若干询问操作，每次询问访问从 $u$ 到 $v$ 上面的所有轻重链一次。例如在上图的剖分方式中，查询 $3$ 到 $8$ 一共访问了 $3$ 条：轻链 1-3，重链 1-4，轻链 4-8；查询 $3$ 到 $11$ 一共访问了 $3$ 条：轻链 1-3，轻链 1-2，重链 2-11。 大宁请你给出一种剖分方案，使所有询问操作总共访问的**轻重链总条数**最小，由于可能有许多合法方案，请任意输出一种，我们提供 Special Judge 检验你的方案的正确性。 设你的剖分方式的查询链数为 $x$，std 答案的查询数为 $x_0$，评分参数为 $a$。 你得到的分数是： - $10$ 分：当 $x\leq x_0$ 。 - $8$ 分：当 $0

第一行有两个正整数 $n$ 和 $q$ ，表示该树的节点数 $n$ 和查询次数 $q$。 接下来 $n-1$ 行，各有两个正整数 $u,v$ ，表示 $u$ 和 $v$ 之间有一条边。 接下来 $q$ 行为 $q$ 个询问，为 $U,V$，表示有一次从 $U$ 到 $V$ 的询问。

一共 $n$ 行，对于 $i$ 号节点，如果它不是叶子节点，那么输出它在你的剖分方案里的重儿子，否则输出 $0$。

样例即为上图，但图上的剖分方式对于此处的查询并非最优。 对于 $20\%$ 的数据，$n,q\le10$； 对于 $60\%$ 的数据，$n,q\le1000$； 对于 $100\%$ 的数据，$1\le n\le100000$，$1\le q\le200000$ ,保证给出的是一棵合法的树。 [Div\_Checker 下载](https://pan.baidu.com/s/1c26OLf6) 如果对 Checker 的使用方式不太理解，请参照下面的图片： 图中数据为样例。  一个合法方案的输出。  不合法方案的输出。  --- $\text{upd 2022.8.26}$：新增加一组 Hack 数据。