Cho một mạng máy tính gồm \(n\) máy tính. Các máy tính được kết nối với nhau theo các cặp \((u,v)\) có ngghiax là máy tính thứ \(u\) được nối trực tiếp với máy tính thứ\(v\). Khi đó giữa hai máy tính \(u,\ v\) có thể truyền dữ liệu cho nhau. Có tất cả \(n - 1\) các cặp nối và đảm bảo các cặp máy tính đều được kết nối với nhau theo các trực tiếp hoặc gián tiếp.

Để chuyển dữ liệu một cách mượt mà, các khách hàng có những yêu cầu rất đặc biệt theo dạng \(a\ b\ k\ (1 \leq a,b \leq n;a
eq b;1 \leq k \leq 10^{6})\) với ý nghĩa khách hàng này muốn truyền một lượng dữ liệu nào đó từ máy \(a\) tới máy \(b\) và tốc độ truyển tải tối thiểu trong các cặp nối để truyền dữ liệu từ máy \(a\) đến máy \(b\) bằng \(k\).

Yêu cầu: Với mỗi cặp nối \((u,v)\) tìm một giá trị \(f\) là tốc độ truyền tải thỏa mãn yêu cầu của \(m\) khách hàng.

Dữ liệu vào:

+ Dòng 1: Chứa số nguyên dương \(n\ (2 \leq n \leq 10^{5})\);

+ \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,\ v\) mô tả cặp nối \((u,v)\)

+ Dòng tiếp theo chứa số nguyên dương \(m(1 \leq m \leq 10^{5})\) là số lượng khách hàng.

+ \(m\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(a_{i},\ b_{i},\ k_{i}\left( 1 \leq a_{i},b_{i} \leq n;a_{i}
eq b_{i};1 \leq k_{i} \leq 10^{6} \right)\)

Kết quả:

+ Gồm \(n - 1\) giá trị \(f_{i}\) là tốc độ truyển tải của cặp nối thứ \(i\ \left( 1 \leq f_{i} \leq 10^{6} \right)\) thỏa mãn yêu cầu cảu \(m\) khách hàng. Nếu không tồn tại đpá án thì in ra \(- 1\).

Lưu ý, đối với nhưng cặp nối không có các ràng buộc về yêu cầu của khách hàng, có thể in ra một số nguyên bất kỳ trong đoạn \(\lbrack{1,10}^{6}\rbrack\)

Ví dụ:

Input	Output		Input	Output		Input	Output
4 1 2 3 2 3 4 2 1 2 5 1 3 3	5 3 5		6 1 2 1 6 3 1 1 5 4 1 4 6 1 3 3 4 1 6 5 2 1 2 5	5 3 1 2 1		6 1 2 1 6 3 1 1 5 4 1 4 6 1 1 3 4 3 6 5 3 1 2 4	-1

Giải thích ví dụ:

+ Ở ví dụ 1, mạng máy tính có dạng đường thẳng \(1 - 2 - 3 - 4\).

• Yêu cầu của khách hàng đầu tiên muốn tốc độ truyền tải tối thiểu từ máy 1 tới máy 2 (cặp nối trực tiếp) chính xác bằng 5.

• Khách hàng thứ hai muốn đoạn đường từ máy 1 tới máy 3 có tốc độ tối thiểu chính xác bằng 3. Để truyền từ máy 1 tới máy 3 có thể thực hiện theo 2 cặp \((1,2)\) và \((3,2)\) nên cặp \((3,2)\) phải có tốc độ truyền tải là 3 vì \(3 = min(3,5)\).

• Với cặp khách hàng \((3,4)\): do không có yêu cầu nào của khách hàng ràng buộc, ta có thể chọn một giá trị bất kì trong đoạn \(\lbrack{1,10}^{6}\rbrack\)

Hình minh họa test ví dụ thứ 1

Hình minh họa test ví dụ thứ 2

+ Ở ví dụ 3, ta không thể có đáp án vì yêu cầu của khách hàng thứ nhất và thứ 3 không thể đồng thời thực hiện được.

Ràng buộc:

+ Subtask 1 \((20\%)\): \(m = 1\)

+ Subtask 2 (\(30\%)\): cặp nối thứ \(i\) có dạng \((i,i + 1)\)

+ Subtask 3 (30%): \(n,m \leq 5000\)

+ Subtask 4 (20%): Không có ràng buộc gì thêm