Gaurav and Unique Edges

0

0 votes
Medium
Problem

Mr Gaurav is trying to solve one graph problem. The problem says, Given N nodes and N-1 edges connecting the nodes. There is a unique path between each pair of nodes. Each edge has some weight w. Q queries are given, for each query, find no of unique edge weights present in the path connecting u and v. Since Gaurav is President of CSS, he has got some urgent work. So, he asked you to solve the problem for him.

Input

First line of input contains a single integer N.

Next N-1 lines contains 3 space separated integer u, v, w representing an edge connecting u and v and having weight w.

Next line contains a single integer Q.

Next Q lines contains 2 space separated integer u and v.

Output

Print Q lines and each line should print one integer denoting the count of unique edges present in the path between u and v.

Constraints

2 ≤ N,Q ≤ 100 000

1 ≤ u,v ≤ 100 000

1 ≤ w ≤ 10

Setter : Sourav Kumar Paul

Sample Input
7
1 2 3
2 3 1
2 4 1
1 5 2
5 6 1
5 7 2
2
3 6
1 7
Sample Output
3
1
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

Query 1 : Edges are : (3,2) -1, (2,1) - 3, (1,5) - 2, (5,6) - 1

So, no of unique edges are 3.

Editor Image

?