Thành phố Hotham có \(N\) hồ chứa nước, nối với nhau bởi \(M\) đường ống. Mạng lưới liên thông: từ bất kỳ hồ nào cũng có thể đi đến bất kỳ hồ khác qua các đường ống. Mỗi ống nối hai hồ khác nhau và giữa hai hồ có nhiều nhất một ống.

Tên tội phạm Jester đang rút nước khỏi một số ống và bơm nước vào một số ống khác. Lượng nước hắn rút hoặc bơm tại mỗi ống luôn là một số nguyên chẵn mét khối mỗi giây. Nếu hắn rút \(2d\) mét khối mỗi giây khỏi ống nối \(u\) và \(v\), mỗi hồ mất \(d\) mét khối mỗi giây. Nếu hắn bơm \(2p\) mét khối mỗi giây vào ống đó, mỗi hồ nhận thêm \(p\) mét khối mỗi giây.

Các cảm biến chỉ đo được độ biến thiên ròng \(c_i\) của mỗi hồ, bằng tổng lượng nhận thêm trừ tổng lượng mất đi từ các ống kề với hồ đó. Thị trưởng muốn biết liệu các số đo này có xác định duy nhất lượng nước được bơm vào hoặc rút khỏi từng ống hay không. Nếu có, hãy tìm các lượng đó. Các ống không nhất thiết có cùng lượng nước bị tác động.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên \(c_i\), là độ biến thiên ròng của hồ \(i\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(u_i,v_i\), cho biết ống thứ \(i\) nối hai hồ này. Các hồ được đánh số từ \(1\) đến \(N\). Dữ liệu bảo đảm tồn tại ít nhất một cách bơm và rút nước thỏa mãn mọi số đo.

Dữ liệu ra

Nếu không thể xác định duy nhất kế hoạch của Jester, in một dòng chứa \(0\).

Nếu có duy nhất một kế hoạch, in \(M\) dòng. Dòng thứ \(i\) chứa số nguyên \(x_i\), là toàn bộ lượng nước Jester tác động lên ống thứ \(i\) trong một giây: dương nếu bơm vào, âm nếu rút ra và bằng \(0\) nếu không tác động. Mỗi hồ ở hai đầu ống nhận độ biến thiên \(x_i/2\) từ ống này; vì thế

Ràng buộc

• \(1 \le N \le 100\,000\), \(1 \le M \le 500\,000\).
• \(1 \le u_i,v_i \le N\), \(u_i \ne v_i\); đồ thị đơn và liên thông.
• \(-10^9 \le c_i \le 10^9\).
• Nếu kế hoạch là duy nhất thì \(-10^9 \le x_i \le 10^9\).

Phân nhóm

• \(30\) điểm: mạng lưới là một cây.
• \(70\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

4 3
-1
1
-3
1
1 2
1 3
1 4

2
-6
2

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

0