Đất nước có tổng cộng ~n~ thành phố và ~m~ con đường hai chiều độ dài ~1~ nối giữa chúng sao cho xuất phát từ một thành phố có thể đi đến bất kỳ thành phố khác. Mỗi thành phố có xây dựng một khách sạn.

Malnar ghé thăm đất nước và đã dự tính ở lại khách sạn thuộc một trong ~n~ thành phố. Ngoài ra, Malnar còn lưu lại khoảng cách ngắn nhất từ khách sạn đến các thành phố khác. Tuy nhiên, vì tuổi đã cao nên Malnar lại không nhớ chính xác đã lựa chọn khách sạn thuộc thành phố nào, mà chỉ lưu lại một vài thông tin của danh sách các khoảng cách ngắn nhất từ khách sạn đến các thành phố khác.

Dựa trên thông tin của danh sách, bạn hãy giúp Malnar xác định các khách sạn ở các thành phố nào có thể lựa chọn.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n \le 5.10^4; \; n-1 \le m \le 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~ và ~v_i~ ~(1 \le u_i,v_i \le n; \; u_i \neq v_i)~ mô tả đường nối giữa hai thành phố ~u_i~ và ~v_i~. Có tối đa một con đường nối giữa hai thành phố.
• Dòng cuối cùng chứa ~n~ số nguyên, số nguyên thứ ~i~ hoặc là một giá trị nguyên ~d_i~ ~(0 \le d_i < n)~ biểu thị khoảng cách ngắn nhất từ khách sạn đến thành phố ~i~, hoặc là giá trị ~-1~ biểu thị thông tin không còn được lưu lại đối với thành phố này.

Output

• Dòng đầu tiên in ra số lượng thành phố thỏa mãn. Dòng thứ hai in ra danh sách các thành phố thỏa mãn theo thứ tự tăng dần.

Samples

Sample Input 1

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

Sample Output 1

2
4 6

Sample Input 2

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

Sample Output 2

2
3 5

Sample Input 3

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

Sample Output 3

0

Scoring

• Subtask ~1~ với ~25\%~ số điểm: ~m+1=n\le5000; u_i+1=v_i \; \forall \; i~
• Subtask ~2~ với ~25\%~ số điểm: ~d_i=-1 \; \forall \; i>1~
• Subtask ~3~ với ~25\%~ số điểm: ~n,m \le 5000~
• Subtask ~4~ với ~25\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

• Trong ví dụ đầu tiên, khoảng cách từ thành phố ~4~ đến thành phố ~1~ và ~7~ lần lượt là ~2~ và ~3~, vì vậy có thể lựa chọn khách sạn ở thành phố ~4~. Tương tự với thành phố ~6~.