Đồ thị không có đường đi dài

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh. Đồ thị không có khuyên (cạnh nối một đỉnh với chính nó) và không có cạnh bội.

Bạn cần định hướng tất cả các cạnh (biến mỗi cạnh vô hướng thành một cung có hướng) sao cho đồ thị có hướng thu được không chứa bất kỳ đường đi nào có độ dài từ $2$ trở lên (độ dài đường đi tính bằng số cung đi qua).

Nếu tồn tại nhiều cách định hướng thỏa mãn, in ra một cách bất kỳ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đỉnh và số cạnh.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i,v_i$: cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$.

Dữ liệu ra

• Nếu không tồn tại cách định hướng thỏa mãn, in ra NO.
• Ngược lại, in ra YES ở dòng đầu. Dòng thứ hai in một xâu nhị phân độ dài $m$: ký tự thứ $i$ là 0 nếu cạnh thứ $i$ được định hướng từ $u_i$ đến $v_i$, và là 1 nếu định hướng từ $v_i$ đến $u_i$.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $n-1\le m\le 2·{10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• Đồ thị liên thông, không có khuyên và cạnh bội.

Ví dụ