Bob là một thành viên tích cực của câu lạc bộ LHP-IT. Cậu có niềm đam mê nghiên cứu đồ thị với cấu trúc dữ liệu dạng cây trong đồ thị. Lần này, cậu đang quan sát một cây thì thấy có \(N\) đỉnh, đánh số từ \(1\) đến \(N\) và \(N - 1\) cạnh, đánh số từ \(1\) đến \(N - 1\). Cạnh thứ \(i (1 \le i \le N - 1)\) nối đỉnh \(U_i\) với đỉnh \(V_i\) có trọng số \(W_i\) không âm (\(W_i \lt 2^{20}\)).

Nhiệm vụ

Một hôm, Bob lấy mẩu giấy ra để xem lại cây này thì phát hiện ra trọng số đã bị nhòe do không khí bị ẩm móc, còn phần còn lại về số lượng đỉnh và thông tin các cạnh thì vẫn có thể đọc được. Cậu mong muốn tìm lại được trọng số của các cạnh trên cây.

Bob ngồi ngẫm nghĩ và nhớ được \(M\) mẫu thông tin, mẫu thông tin thứ \(i (1 \le i \le M)\) cho biết tổng trọng số các cạnh trên đường đi từ đỉnh \(A_i\) đến đỉnh \(B_i\), sau khi lấy dư cho \(2^{20}\) là \(C_i\).

Yêu cầu

Hãy giúp Bob tìm lại trọng số của các cạnh trên cây STREE nếu có thể. Lưu ý:
- Các mẫu thông tin của Bob đưa ra có thể mâu thuẫn nhau, hoặc không thỏa mãn các ràng buộc, hoặc thiếu thông tin để kết luận.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(N\) thể hiện số đỉnh của cây (\(1 \le N \le 10^5\)).
• Dòng thứ \(i\) trong số \(N - 1\) dòng tiếp theo chứa hai số nguyên dương \(U_i\), \(V_i\) thể hiện cạnh thứ \(i\) của cây (\(1 \le U_i, V_i \le N\)).
• Dòng tiếp theo chứa một số nguyên không âm \(M\) thể hiện số mẫu thông tin mà Bob nhớ được (\(0 \le M \le 2 \times 10^5\)).
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\) thể hiện mẫu thông tin thứ \(i\) (\(1 \le A_i, B_i \le N\); \(0 \le C_i \lt 2^{20}\)).

Tất cả các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

• Nếu tồn tại một đáp án duy nhất, hãy in ra từ \(UNIQUE\).
• Tiếp theo là một dòng mới gồm \(N - 1\) giá trị, giá trị thứ \(i\) thể hiện trọng số \(W_i\).
• Các số trên cùng một dòng cách nhau bởi dấu cách.
• Trái lại, hãy in ra từ \(INDETERMINATE\).

Input 1

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

Output 1

UNIQUE
1 1

Giải thích

• Trọng số của hai cạnh tìm lại được đều là \(1\)

Input 2

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

Output 2

INDETERMINATE

Giải thích

Hai mẫu thông tin tương ứng với hai phương trình:

• \(W_1 = 5\)
• \(W_1 + W_2 = 2\)

Giải hệ có \(W_1 = 5\) và \(W_2 = -3\) không thỏa mãn điều kiện trọng số không âm.

Input 3

3
1 2
2 3
1
1 3 2

Output 3

INDETERMINATE

Giải thích:
Mẫu thông tin duy nhất cho 3 đáp án (W_1, W_2) thỏa mãn, đó là: {(0,2), (1,1), (2,0)}.

Subtasks

• Subtask 1 (20%): \(N, M \le 3\) và \(W_i \le 10\), \(∀ i = 1,...,N\)
• Subtask 2 (20%): \(N, M \le 6\) và \(W_i \le 10\), \(∀ i = 1,...,N\)
• Subtask 3 (20%): \(A_i = 1\), \(∀ i = 1,...,M\)
• Subtask 4 (20%): \(U_i = i\), \(V_i = i+1\), \(∀ i = 1,...,N-1\) và \(A_i \le A_{i+1}\), \(B_i \le B_{i+1}\), \(∀ i = 1,...,M-1\)
• Subtask 5 (10%): Bậc của mọi đỉnh trên cây tối đa là 2.
• Subtask 6 (10%): Không có ràng buộc nào thêm.