有一个包含 $n$ 个顶点的无向图 $G$。它有一个有趣的性质：如果我们把多重边视为一条边，图 $G$ 将成为一棵树。Alice 和 Bob 发明了以下游戏：

• 游戏开始时，Alice 和 Bob 选择两个顶点 $S$ 和 $T$，$S \neq T$。
• 存在另一个包含 $n$ 个顶点的图 $H$，初始时没有任何边。
• 在每一轮中，当前玩家选择图 $G$ 中的任意一条边 $u - v$，将其删除，并改变图 $H$ 中边 $u - v$ 的状态：如果图 $H$ 中原本没有这条边，则添加它；如果图 $H$ 中原本有这条边，则将其删除。
• 如果某一时刻图 $H$ 中存在一条从 $S$ 到 $T$ 的路径，则 Alice 获胜。
• 如果图 $G$ 中没有边且 Alice 尚未获胜，则 Bob 获胜。
• 玩家轮流行动，Alice 先手。

孩子们非常喜欢这个游戏，他们一共玩了 $q$ 次。现在他们想知道，如果双方都采取最优策略，每局游戏谁会获胜。请帮他们找出答案！

输入格式

第一行包含两个整数 $n$ 和 $q$：图 $G$ 中的顶点数和 Alice 与 Bob 进行的游戏次数（$2 \le n \le 10^5$，$1 \le q \le 10^5$）。

接下来的 $n - 1$ 行包含图 $G$ 的描述。每行包含三个整数 $a$、$b$ 和 $c$（$1 \le a, b \le n$，$1 \le c \le 10^9$），表示顶点 $a$ 和 $b$ 之间恰好有 $c$ 条边。保证如果将所有的 $c$ 变为 $1$，图 $G$ 将成为一棵包含 $n$ 个顶点的树。

接下来的 $q$ 行描述了每局游戏。每行包含两个整数 $S$ 和 $T$：游戏的参数（$1 \le S, T \le n$，$S \neq T$）。

输出格式

对于每局游戏，如果 Alice 获胜，输出 $1$，否则输出 $2$。答案之间用换行符分隔。

样例

输入 1

6 5
1 2 3
1 3 2
2 4 1
2 5 2
3 6 2
1 4
5 4
5 6
2 6
4 6

输出 1

1
1
2
2
2