Ông Malnar cuối cùng cũng đã đến kỳ nghỉ hàng năm của mình. Đất nước mà anh ấy quyết định đi du lịch có thể được biểu diễn dưới dạng ~n~ thành phố có số hiệu từ ~1~ đến ~n~ và ~m~ con đường hai chiều nối chúng. Tất cả các con đường đều có cùng độ dài và có thể đến bất kỳ thành phố nào từ bất kỳ thành phố nào khác bằng cách đi trên những con đường này. Một đường đi từ thành phố ~a~ đến thành phố ~b~ được định nghĩa là một chuỗi các con đường sao cho bắt đầu từ thành phố ~a~ và tuần tự đi qua các con đường theo trình tự đó sẽ đến thành phố ~b~. Độ dài của một đường đi từ thành phố ~a~ đến thành phố ~b~ được định nghĩa là số lượng con đường trên đường đi đó.

Ông Malnar thường xuyên đặt phòng khách sạn đắt nhất ở một trong ~n~ thành phố và sau đó bắt đầu lên kế hoạch cho chuyến hành trình của mình. Để thuận tiện cho việc lập kế hoạch của mình, anh ấy đã ghi lại độ dài của đường đi ngắn nhất cần thiết từ khách sạn đến từng thành phố. Khoảng cách từ khách sạn đến thành phố ~i~ là độ dài của đường ngắn nhất từ khách sạn đến thành phố ~i~.

Quá hào hứng với kỳ nghỉ đã chờ đợi từ lâu của mình, ông Malnar hoàn toàn quên mất khách sạn nằm ở thành phố nào. Anh ấy chắc chắn không muốn bỏ lỡ chuyến đi nên yêu cầu bạn xác định xem khách sạn có thể tọa lạc ở thành phố nào.

Xác định tất cả các thành phố có thể là vị trí đặt khách sạn dựa trên khoảng cách đã cho.

Input

• Dòng đầu tiên chứa các số tự nhiên ~n~ và ~m~ tương ứng là số thành phố và số con đường nối chúng (~1 \le n < 5 \times 10^4~; ~1 \le m \le 10^5~);
• Ở dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa 2 số ~u_i~ và ~v_i~ mô tả một con đường nối giữa thành phố ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \neq v_i~). Biết rằng có nhiều nhất một con đường nối giữa hai thành phố bất kỳ;
• Ở dòng cuối cùng có ~n~ số nguyên cho biết số thứ ~i~ biểu thị khoảng cách ~d_i~ từ thành phố thứ ~i~ đến thành phố nơi có khách sạn hoặc -1 nếu ông Malnar không ghi lại khoảng cách đó (~1 \le d_i < n~).

Output

• Ở dòng đầu tiên, hãy viết số lượng thành phố nơi khách sạn có thể tọa lạc;
• Ở dòng thứ hai, viết nhãn của các thành phố nơi có thể đặt khách sạn, theo thứ tự tăng dần.