Hy vọng rằng bạn biết cách tìm đường kính của cây. Đó là phần đầu tiên trong các khái niệm cơ bản về cây! Nhưng bài tập này hoàn toàn khác: bây giờ, bạn cần tìm chu vi của một cái cây!

Có thể bạn đã biết, pi bằng tỷ số giữa chu vi và đường kính của một thứ gì đó. Ngoài ra, có thể bạn chưa biết, toán học là một lời nói dối và số pi thực sự bằng ~3~. Có tin đồn rằng đó là nơi bắt nguồn của con số tree(3) .

Giả sử số pi bằng ~3~ thì chu vi của cái cây đã cho là bao nhiêu?

Input

• Dòng đầu chứa một số nguyên ~n~ (~1 \le n \le 3 \times 10^5~) là số đỉnh của cây.

• ~n - 1~ dòng tiếp theo mô tả các cạnh của cây. Dòng thứ ~i~ gồm ~2~ số nguyên ~u_i,\ v_i~ ~(1 \le u_i, v_i \le n,\ u_i \neq v_i)~ thể hiện có cạnh nối giữa đỉnh ~u_i~ và ~v_i~. Dữ liệu đảm bảo các cạnh tạo thành một cây.

Output

In ra một số nguyên duy nhất là chu vi của cây.

Sample 1

Input

1

Output

0

Sample 2

Input

3
3 2
2 1

Output

6

Sample 3

Input

5
4 2
1 4
5 4
3 4

Output

6

Bạn được cho ~n+1~ đỉnh và ~n-1~ cạnh, ~n~ đỉnh đầu tiên tạo thành một cây và đỉnh ~n+1~ không được nối với bất kì đỉnh nào khác. Với mỗi đỉnh từ ~1~ đến ~n~, hãy trả lời câu hỏi sau:

Nếu một cạnh nối giữa đỉnh ~i~ và đỉnh ~n+1~ được thêm vào, đường kính của cây được tạo thành là bao nhiêu? (Nhận thấy tất cả ~n+1~ đỉnh sẽ tạo thành một cây sau khi thêm cạnh này vào)

Input

Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \le n \le 3 \times 10^5)~ là số đỉnh trong cây ban đầu.

~n-1~ dòng tiếp theo mô tả các cạnh của cây. Dòng thứ ~i~ chứa ~2~ số nguyên ~u_i~, ~v_i~ ~(1 \le u_i, v_i \le n,\ u_i \neq v_i)~ thể hiện có cạnh nối giữa đỉnh ~u_i~ và ~v_i~. Dữ liệu đảm bảo các cạnh tạo thành một cây.

Output

In ra ~n~ dòng, mỗi dòng chứa đường kính của cây được tạo thành sau khi thêm một cạnh nối giữa đỉnh ~i~ và đỉnh ~n+1~.

Sample 1

Input

1

Output

1

Sample 2

Input

3
3 2
2 1

Output

3
2
3

Sample 3

Input

5
4 2
1 4
5 4
3 4

Output

3
3
3
2
3

Như các bạn đã biết, lười sống trên cây. David có một chú lười làm thú cưng và anh thường cho nó chơi với những chiếc cây (không trọng số) trong khi anh giải các bài toán lập trình. Thỉnh thoảng, David thấy rằng chú lười đang đứng ở đỉnh ~a~ trên cây, và yêu cầu nó di chuyển đến một đỉnh ~b~ khác.

Đương nhiên, chú lười rất nghe lời David, nhưng lượng năng lượng còn lại chỉ cho phép nó di chuyển qua tối đa ~c~ cạnh. Nếu chú lười cần di chuyển qua ít hơn ~c~ cạnh để đến đỉnh ~b~, nó sẽ đến ~b~ và ngủ một giấc. Nếu không, chú lười sẽ đến gần ~b~ nhất có thể trước khi dừng lại và đứng yên tiêu hóa thức ăn.

Vậy chú lười sẽ dừng lại ở đâu? Vì chuyện này xảy ra khá thường xuyên, David muốn nhờ bạn trả lời ~q~ câu hỏi có dạng như nhau.

Input

Dòng đầu tiên chứa một số nguyên ~n~, là số đỉnh trên cây. ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ miêu tả các cạnh trong cây. Dữ liệu đầu vào đảm bảo các cạnh này tạo thành một cây.

Dòng tiếp theo chứa một số nguyên ~q~, là số lần David sẽ yêu cầu chú lười di chuyển. ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a~, ~b~, và ~c~ lần lượt là đỉnh mà chú lười đang đứng, đỉnh mà David yêu cầu chú lười di chuyển tới, và lượng năng lượng của chú lười khi bắt đầu di chuyển.

~1 \le n, q \le 3 \times 10^5~

~1 \le a, b, c, u, v \le n~

Output

Với mỗi câu hỏi, in ra một số nguyên là số thứ tự của đỉnh mà chú lười sẽ dừng lại sau câu hỏi đó.

Sample 1

Input

1
1
1 1 1

Output

1

Sample 2

Input

3
3 2
2 1
3
2 2 2
1 1 2
3 3 3

Output

2
1
3

Sample 3

Input

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

Output

5
5
5
5
5

Cho một đồ thị liên thông vô hướng có trọng số gồm ~n~ đỉnh và không có chu trình. Với ~q~ cặp đỉnh khác nhau, bạn phải tìm luồng cực đại từ đỉnh đầu tiên tới đỉnh còn lại trong cặp.

Luồng cực đại trong một đồ thị giữa hai đỉnh ~a~ và ~b~ được định nghĩa như sau: Bạn có thể chọn bất kì đường đi nào từ ~a~ tới ~b~ sao cho mỗi cạnh trên đường đi đó đều có một trọng số dương. Sau đó, hãy trừ đi ~1~ đơn vị ở trọng số của mỗi cạnh trên đường đi đó, đồng thời cộng thêm ~1~ vào kết quả. Cứ làm như vậy bao nhiêu lần tùy ý. Giá trị "luồng cực đại" khi đó là kết quả lớn nhất mà bạn có thể đạt được, mỗi bước bạn có thể chọn lại đường đi từ ~a~ đến ~b~ sao cho tối ưu nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~, là số đỉnh và số cạnh của đồ thị. ~(2 \leq n,m \leq 3*10^5)~

• Mỗi dòng trong số ~m~ dòng tiếp theo bao gồm ~3~ số nguyên dương ~u~ ~v~ ~w~, lần lượt là số hiệu hai đỉnh của một cạnh và trọng số ban đầu của cạnh đó. ~(1 \leq w \leq 10^9, u \neq v)~

• Dòng tiếp theo chứa số nguyên dương ~q~: số lượng truy vấn mà bạn phải trả lời. ~(1 \leq q \leq 3*10^5)~

• Mỗi dòng trong số ~q~ dòng tiếp theo chứa hai số nguyên ~a~ và ~b~, chính là hai đỉnh mà bạn phải tìm luồng cực đại giữa chúng trong truy vấn đó. ~(1 \leq a,b \leq n, a \neq b)~

Dữ liệu đảm bảo đồ thị không có chu trình, khuyên hay cạnh trùng.

Output

• Với mỗi truy vấn, in ra một số nguyên duy nhất là giá trị luồng cực đại giữa hai đỉnh ~a~ và ~b~ trong truy vấn đó.

Sample 1

Input

2 1
1 2 2768
2
1 2
2 1

Output

2768
2768

Sample 2

Input

3 2
3 2 4814
2 1 1832
3
2 1
1 2
3 1

Output

1832
1832
1832

Sample 3

Input

5 4
4 2 10348
1 4 2690
5 4 9807
3 4 8008
5
5 4
1 5
5 4
5 4
1 5

Output

9807
2690
9807
9807
2690

Sample 4

Input

5 4
1 3 2653
4 1 322
5 1 8657
2 4 4896
5
4 2
2 5
2 5
1 3
4 5

Output

4896
322
322
2653
322

Ghi chú

Bạn phải trả lời các truy vấn online. Ban đầu, tác giả định bắt bạn làm như vậy bằng cách mã hóa các dữ liệu đầu vào, nhưng điều này làm cho bài toán khó hơn và khi đọc cảm thấy khó chịu. Vì vậy, hãy tự giác trả lời hết truy vấn thứ nhất, rồi đến truy vấn thứ hai và lần lượt sau đó.

Chúng ta đang luyện tập để ngày một tiến bộ hơn thôi, đúng không ^^

Đề gốc được viết bằng thơ, dựa trên The Lorax. Bạn đọc hứng thú có thể xem bài gốc trên Codeforces. Dưới đây là tóm tắt của đề bài.

Tôi là Lorax, tôi nói cho Cây!

Thần rừng Lorax muốn nhờ bạn trồng cây trong thành phố Thneedville. Thành phố được mô tả bằng một đồ thị liên thông gồm ~n~ đỉnh và ~n-1~ cạnh. Bạn phải giúp thần Lorax tổng cộng ~q~ lần, mỗi lần đặt ~x_i~ hạt giống và ~x_i~ chậu cây tại hai đỉnh khác nhau ~a_i~ và ~b_i~. Tuy nhiên nếu ~x_i = 0~, bạn sẽ phải trả lời câu hỏi sau:

Nếu hiện giờ bạn phải nối mỗi hạt giống với mỗi chậu cây trong thành phố sao cho tổng khoảng cách giữa mỗi cặp là nhỏ nhất có thể, có bao nhiêu cặp sẽ đi qua cạnh nối giữa ~a_i~ và ~b_i~?

Input

Dòng đầu tiên chứa số nguyên ~c~ ~(1 \le c \le 20)~ là số lượng test. Mỗi test gồm:

• Với mỗi test, dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n, q \le 10^5)~ lần lượt là số đỉnh trong Thneedville và số lần bạn cần giúp thần Lorax.

• ~n-1~ dòng tiếp theo mô tả các cạnh trong Thneedville. Dòng thứ ~i~ chứa hai số nguyên ~u_i~, ~v_i~ ~(1 \le u_i, v_i \le n,\ u_i \neq v_i)~ thể hiện có cạnh nối giữa đỉnh ~u_i~ và ~v_i~.

• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a_i~, ~b_i~, ~x_i~ ~(1 \le a_i, b_i \le n,\ a_i \neq b_i,\ 0 \le x \le 10^8)~. Nếu ~x_i=0~, bạn cần in ra số lượng cặp hạt giống - chậu cây đi qua cạnh nối giữa ~a_i~ và ~b_i~ (đảm bảo sẽ có cạnh nối trực tiếp giữa ~a_i~ và ~b_i~). Nếu ~x_i>0~, bạn cần đặt ~x_i~ hạt giống tại đỉnh ~a_i~ và ~x_i~ chậu cây tại đỉnh ~b_i~.

Output

Với mỗi câu hỏi có ~x_i=0~, in ra một số nguyên duy nhất là số lượng cặp hạt giống - chậu cây đi qua cạnh nối giữa ~a_i~ và ~b_i~.

Sample Input

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

Sample Output

5
3
0
5
4
1

Có thể bạn đã từng nghe qua câu nói: "Tiền không mọc trên cây". Hiển nhiên, người nghĩ ra câu nói đó trông có vẻ như không có tí kiến thức gì về thực vật học cũng như về lập trình. Bạn đã được học rằng, tạo ra một cây để "mọc ra tiền" là điều rất tầm thường. Vì vậy, đây mới là thử thách thực sự:

Bạn có một gốc cây mọc ra tiền ở đỉnh ~1~, và tất cả các đỉnh đều có một giá trị nhất định. Giá trị của cây con của đỉnh ~x~ sẽ bằng tích của tất cả các giá trị của các đỉnh thuộc cây con ấy. Ban đầu, tất cả các đỉnh có giá trị ~1~.

Bây giờ, có ~q~ truy vấn dạng t x y:

• Nếu ~t = 1~, bạn sẽ cho đỉnh ~x~ một loại phân bón đặc biệt, chuyển giá trị của nó thành ~y~.

• Nếu ~t = 2~, một khách hàng sẽ đến và hỏi rằng: "Giá trị cây con gốc ~x~ gấp giá trị cây con gốc ~y~ bao nhiêu lần?". Hơn nữa, vì bạn không thích những số quá lớn, nên nếu đáp án lớn hơn ~10^9~, hãy in ra 1000000000.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~, số đỉnh của cây. ~(1 \leq n \leq 3 \times 10^5)~

• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương khác nhau, mô tả một cạnh ở trên cây. Những cạnh này sẽ tạo thành một cây.

• Dòng tiếp theo chứa một số nguyên ~q~, số lượng các truy vấn. ~(1 \leq q \leq 3 \times 10^5)~

• ~q~ dòng tiếp theo là các truy vấn, mỗi truy vấn có dạng t x y như đã mô tả ở trên. ~(1 \leq t \leq 2,\ 1 \leq x,y \leq n)~

Output

• Với mỗi truy vấn loại ~2~, in ra một dòng chứa một số thực duy nhất là câu trả lời cho câu hỏi: "Giá trị cây con gốc ~x~ gấp giá trị cây con gốc ~y~ bao nhiêu lần?" Nếu kết quả lớn hơn hoặc bằng ~10^9~ hãy in ra ~1000000000~.

• Đối với mọi truy vấn, kết quả của bạn sẽ được chấp nhận nếu giống hoàn toàn hoặc chênh lệch so với đáp án tác giả đưa ra không quá ~10^{-6}~.

Sample 1

Input

1
1
1 1 1

Output

Sample 2

Input

3
3 2
2 1
3
2 2 2
2 1 2
2 3 3

Output

1.0000000000
1.0000000000
1.0000000000

Sample 3

Input

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

Output

1.0000000000
1.0000000000