Đề bài

“Bắt được tớ, bắt được tớ, tớ sẽ mua báo cho cậu!” là một câu hát trò chơi phổ biến của trẻ em Croatia.

Ankica và Branko đang chơi đuổi bắt trên một đồ thị vô hướng liên thông. Branko di chuyển trên đồ thị, còn Ankica cố bắt cậu. Trò chơi diễn ra theo lượt; mỗi lượt gồm các bước sau:

• Ankica đoán vị trí của Branko, cụ thể là đoán rằng Branko đang ở một đỉnh nào đó. Nếu đoán đúng, Branko bị bắt và trò chơi kết thúc. Nếu đoán sai:
• Branko đi qua một cạnh kề với vị trí hiện tại, tức là chuyển sang một đỉnh kề. Branko không được đứng yên tại vị trí hiện tại.

Cho một đồ thị, hãy xác định Ankica có một chiến lược hữu hạn luôn bắt được Branko hay không, bất kể Branko chơi như thế nào và bắt đầu ở đâu.

Một cách hình thức, chiến lược của Ankica được biểu diễn bằng mảng \(A=(a_1,a_2,\ldots,a_k)\), trong đó \(a_i\) là đỉnh Ankica đoán ở lượt thứ \(i\).

Tương tự, các vị trí của Branko được biểu diễn bằng mảng \(B=(b_1,b_2,\ldots,b_k)\), trong đó \(b_i\) là đỉnh Branko đang đứng trước lượt thứ \(i\). Với mỗi hai phần tử liên tiếp \(b_i\) và \(b_{i+1}\) (\(1\le i<k\)), đồ thị phải có một cạnh nối hai đỉnh đó. Mảng \(A\) không chịu ràng buộc tương tự.

Chiến lược của Ankica được gọi là thành công, tức là bắt được Branko trong không quá \(k\) lượt, nếu với mọi mảng \(B\) hợp lệ có độ dài \(k\), tồn tại một chỉ số \(i\) (\(1\le i\le k\)) sao cho \(a_i=b_i\).

Nếu có chiến lược thành công, hãy tìm một chiến lược làm nhỏ nhất số lượt \(k\).

Bạn vẫn có thể nhận một phần điểm nếu đưa ra chiến lược thành công nhưng không tối ưu, tức là \(k\) chưa nhỏ nhất. Xem mục Chấm điểm để biết chi tiết.

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ủa đồ thị. Các đỉnh được đánh số từ \(1\) đến \(N\).

Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa hai số nguyên \(u_i\) và \(v_i\) (\(1\le u_i,v_i\le N\), \(u_i\ne v_i\)), cho biết có một cạnh vô hướng nối \(u_i\) và \(v_i\).

Không cạnh nào xuất hiện nhiều hơn một lần trong dữ liệu vào và đồ thị luôn liên thông.

Dữ liệu ra

Nếu không tồn tại chiến lược thành công cho Ankica, chỉ in NO trên dòng đầu tiên rồi kết thúc chương trình.

Ngược lại, in YES trên dòng đầu tiên. Dòng thứ hai chứa số lượt \(k\). Dòng thứ ba chứa \(k\) số \(a_1,a_2,\ldots,a_k\) mô tả chiến lược.

Chấm điểm

• Subtask 1 (12 điểm): \(1\le N\le20\).
• Subtask 2 (8 điểm): \(1\le N\le1\,000\), \(M=N-1\), và với mọi \(u=1,\ldots,N-1\), đỉnh \(u\) được nối với đỉnh \(u+1\).
• Subtask 3 (80 điểm): \(1\le N\le1\,000\).

Trên một testcase, nếu chương trình in đúng YES ở dòng đầu tiên nhưng không đưa ra chiến lược thành công, testcase đó nhận \(50\%\) số điểm của subtask chứa nó.

Nếu chương trình in đúng YES ở dòng đầu tiên và đưa ra một chiến lược thành công nhưng không tối ưu, testcase đó nhận \(75\%\) số điểm của subtask chứa nó. Để nhận số điểm này, chiến lược được in phải có không quá \(5N\) lượt. Có thể chứng minh rằng số lượt của chiến lược tối ưu không vượt quá \(5N\).

Điểm của mỗi subtask bằng điểm nhỏ nhất trong các testcase thuộc subtask đó.

Ví dụ

7 6
1 2
1 3
1 4
1 5
1 6
1 7

YES
2
1 1

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

NO