Đồ thị và xâu ký tự

Cho một xâu $s=s_1{s}_2\dots s_n$ chỉ gồm các chữ cái "a", "b" và "c". Từ xâu này người ta dựng một đồ thị vô hướng $G$ gồm $n$ đỉnh (đánh số từ $1$ đến $n$) theo quy tắc sau:

• Với mọi cặp đỉnh $i\ne j$, có một cạnh nối $i$ và $j$ khi và chỉ khi hai chữ cái $s_i$ và $s_j$ bằng nhau hoặc kề nhau trong bảng chữ cái.
• Hai chữ cái được coi là kề nhau nếu chúng là cặp "a"–"b" hoặc "b"–"c". Cặp "a"–"c" không kề nhau.

Sau đó xâu $s$ bị xoá đi, chỉ còn lại đồ thị $G$. Cho trước đồ thị $G$, hãy xác định xem có tồn tại một xâu $s$ nào đó (độ dài đúng bằng $n$, chỉ gồm "a", "b", "c") sao cho đồ thị dựng từ $s$ trùng khớp với $G$ hay không. Nếu có, hãy đưa ra một xâu như vậy.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh và số cạnh của đồ thị $G$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ — một cạnh nối hai đỉnh $u_i$ và $v_i$.

Đảm bảo đồ thị không có cạnh lặp (mỗi cặp đỉnh xuất hiện không quá một lần).

Dữ liệu ra

• Nếu xâu $s$ tồn tại, in ra "Yes" ở dòng đầu, và ở dòng thứ hai in ra một xâu $s$ hợp lệ bất kỳ (độ dài đúng $n$, chỉ gồm "a", "b", "c").
• Ngược lại, in ra "No".

Nếu có nhiều xâu thoả mãn, đưa ra xâu nào cũng được.

Ràng buộc

• $1\le n\le 500$
• $0\le m\le {\displaystyle \frac{n(n-1)}{2}}$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$

Ví dụ