시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
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:
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.
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 2 2 2