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 đối 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ú vị gồm ~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<2^{20})~. Để đảm bảo khỏi quên, cậu đã đặt tên cây này là STREE, viết thông tin về cây này lên một mẩu giấy và cất nó trong ngăn kéo.

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í ẩ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 đơn từ đỉnh ~A_i~ đến đỉnh ~B_i~ sau khi chia 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.

Input

• 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 \cdot 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~ mà Bob nhớ ra ~(1 \le A_i,B_i \le N; 0 \le C_i<2^{20})~.

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

Output

• 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.

Scoring

Mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh được tính theo từng test đơn.

Sample Input 1

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

Sample Output 1

UNIQUE
1 1

Sample Input 2

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

Sample Output 2

INDETERMINATE

Sample Input 3

3
1 2
2 3
1
1 3 2

Sample Output 3

INDETERMINATE

Notes

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

• 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ệ phương trình ta có ~W_1=5~ và ~W_2=-3~. Không thỏa mãn do trọng số phải không âm.

• 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)\}~.