题目描述

你在最近加冕成为了Z国的国王。Z国共有 $n$ 座城市。有 $n-1$ 条无向边将这些城市联通。换句话说，Z国的城市形成了一棵树。

最近你听到了风声，Y国想要进攻Z国的一条路径，以切断Z国城市之间的联系。为此，你决定派兵把守其中的一些城市，以阻挡Y国的攻击。

具体地，我们会收到 $q$ 次询问，每个询问给出树上的两个结点 $u,v$，代表国王听到了Y国要切断从 $u$ 到 $v$ 的路径的风声。你希望派出一些士兵驻扎在一些城市上，使得这些士兵满足如下两个条件：