Ô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ố và ~m~ con đường hai chiều nối chúng. Mỗi con đường 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. Đườ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ự đó, một con đường sẽ đến thành phố ~b~. Độ dài của một con đường được định nghĩa là số lượng đường trên con đường đó.

Ông Malnar thường xuyên đặt phòng khách sạn đắt nhất ở một trong những 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 con đường ngắn nhất cần thiết từ khách sạn đến từng thành phố.

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.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~1 \leq n \leq 5 \times 10^4, n-1 \leq m \leq 10^5~) là số thành phố và số con đường kết nối chúng.
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo gồm hai số nguyên ~u_i~ và ~v_i~ (~1 \leq u_i, v_i \leq n, u_i \neq v_i~), với ý nghĩa có con đường nối giữa hai thành phố ~u_i~ và ~v_i~. Có tối đa một con đường giữa hai thành phố khác nhau bất kì.
• Dòng cuối cùng gồm ~n~ số nguyên ~d_i~ là khoảng cách từ thành phố ~i~ đến thành phố có khách sạn (~1 \leq d_i < n~), ~d_i = -1~ nếu ông Malnar chưa tính được khoảng cách đó.

Output

• Dòng đầu tiên, đưa ra số thành phố mà có thể khách sạn được đặt ở đó.
• Dòng thứ hai là chỉ số của những thành phố mà có thể khách sạn được đặt ở đó, theo thứ tự tăng dần.

Scoring

1. ~m+1=n \leq 5 \times 10^3, u_i+1=v_i \space \forall i~ (10 điểm)

2. ~d_i = -1 \space \forall i >1~ (20 điểm)

3. ~n, m \leq 5 \times 10^3~ (35 điểm)

4. Không có ràng buộc gì thêm (45 điểm)

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

Explanation

Ở ví dụ đầu tiên: đường đi từ thành phố nhãn ~4~ đến thành phố nhãn ~1~ có độ dài ~2~, trong khi đường đi từ thành phố nhãn ~4~ đến thành phố nhãn ~7~ có độ dài ~3~; do đó, thành phố 4 thỏa mãn cả hai điều kiện và khách sạn có thể nằm ở đó; điều tương tự cũng đúng với thành phố được dán nhãn ~6~.