시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 1 1 1 100.000%

문제

There is an undirected graph $G$ with $n$ vertices. It has an interesting property: if we treat multiple edges as one, the graph $G$ will become a tree. Alice and Bob invented the following game:

  • At the beginning, Alice and Bob choose two vertices $S$ and $T$, $S \ne T$.
  • There is another graph $H$ with $n$ vertices and, initially, no edges.
  • On every turn, the current player chooses any edge $u-v$ in graph $G$, deletes it and changes the state of edge $u-v$ in graph $H$: if there was no such edge in graph $H$, it appears, and if there was such an edge, it disappears.
  • Alice wins if there exists a moment of time when there is a path between $S$ and $T$ in graph $H$.
  • If there is no edge in graph $G$ and Alice hasn't won yet, Bob wins.
  • Players take turns, Alice moves first.

Children like the game very much so they have played it $q$ times. Now they are wondering who would win in each game if they were playing optimally. Help them find it out!

입력

The first line of input contains two integers $n$ and $q$: the number of vertices in graph $G$ and the number of games played by Alice and Bob ($2 \le n \le 10^5$, $1 \le q \le 10^5$).

The next $n-1$ lines contain the description of graph $G$. Each line consists of three integers $a$, $b$ and $c$ ($1 \le a, b \le n$, $1 \le c \le 10^9$) which means there are exactly $c$ edges between vertices $a$ and $b$. It is guaranteed that, if we change all $c$ to $1$, the graph $G$ will become a tree with $n$ vertices.

The next $q$ lines describe the games. Each of these lines contains two integers $S$ and $T$: the parameters of the game ($1 \le S, T \le n$, $S \ne T$).

출력

For each game, print 1 if Alice wins, and print 2 otherwise. Separate the answers with line breaks.

예제 입력 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