Cho một đồ thị vô hướng, trong đó mỗi cạnh có một trong hai màu: đen hoặc đỏ. Hãy gán một số thực cho mỗi đỉnh sao cho:

• Với mỗi cạnh đen, tổng hai số ở hai đầu mút bằng \(1\).
• Với mỗi cạnh đỏ, tổng hai số ở hai đầu mút bằng \(2\).
• Tổng giá trị tuyệt đối của tất cả các số được gán là nhỏ nhất có thể.

Nếu không thể gán các số thỏa mãn yêu cầu, hãy thông báo rằng không có cách gán hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số đỉnh và số cạnh. Các đỉnh được đánh số bằng các số nguyên liên tiếp \(1,2,\ldots,N\).

\(M\) dòng tiếp theo mô tả các cạnh. Mỗi dòng chứa ba số nguyên \(a,b,c\), cho biết có một cạnh nối hai đỉnh \(a,b\) và có màu \(c\): \(1\) biểu thị màu đen, \(2\) biểu thị màu đỏ.

Dữ liệu ra

Nếu có lời giải, dòng đầu tiên in YES; dòng thứ hai in \(N\) số cách nhau bởi dấu cách. Số thứ \(i\) (\(1\le i\le N\)) là số được gán cho đỉnh \(i\).

Kết quả phải thỏa mãn:

• Tổng hai số ở hai đầu mút của mỗi cạnh sai khác với giá trị chính xác cần có một lượng nhỏ hơn \(10^{-6}\).
• Tổng giá trị tuyệt đối của tất cả các số được gán sai khác với giá trị nhỏ nhất có thể một lượng nhỏ hơn \(10^{-6}\).

Nếu có nhiều lời giải hợp lệ, có thể in bất kỳ lời giải nào.

Nếu không có lời giải, chỉ in một dòng chứa NO.

Ràng buộc

• \(1\le N\le100\,000\).
• \(0\le M\le200\,000\).
• \(1\le a,b\le N\), \(c\in\{1,2\}\).
• Không có điều kiện \(a\ne b\) hay điều kiện các cặp đầu mút phải khác nhau: đồ thị có thể có khuyên và nhiều cạnh nối cùng một cặp đỉnh.
• Giới hạn thời gian: \(0{,}7\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(5\) điểm: \(N\le5\), \(M\le14\).
2. \(12\) điểm: \(N\le100\).
3. \(17\) điểm: \(N\le1000\).
4. \(24\) điểm: \(N\le10\,000\).
5. \(42\) điểm: không có ràng buộc thêm.

Ví dụ

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

YES
0.5 0.5 1.5 -0.5

2 1
1 2 1

YES
0.3 0.7

3 2
1 2 2
2 3 2

YES
0 2 0

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

NO