Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có \(n\) thành phố và \(m\) chuyến bay. Một thành phố được gọi là thành phố trọng yếu nếu nó xuất hiện trên mọi tuyến đường từ thành phố này đến thành phố khác.
Nhiệm vụ của bạn là tìm tất cả các thành phố quan trọng từ Syrjälä đến Lehmälä.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số thành phố và chuyến bay. Các thành phố được đánh số \(1,2,…, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
- \(m\) dòng sau đó mô tả các tuyến bay. Mỗi dòng ghi hai số nguyên \(a\) và \(b\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Tất cả các chuyến bay là một chiều.
- Dữ liệu đẩm bảo luôn có một tuyến đường từ Syrjälä đến Lehmälä.
Output
- Dòng đầu in số nguyên \(k\): số thành phố trọng yếu.
- Dòng tiếp theo in \(k\) số nguyên: chỉ số của các thành phố trọng yếu theo thứ tự tăng dần.
Constraints
- \(1\leq n \leq 10^5\)
- \(1\leq m \leq 2 ⋅ 10^5\)
- \(1\leq a, b \leq n\)
Example
Sample input
5 5
1 2
2 3
2 4
3 5
4 5
Sample output
3
1 2 5
Bình luận
Có \(n\) thành phố và \(m\) chuyến bay. Một thành phố được gọi là thành phố trọng yếu nếu nó xuất hiện trên mọi tuyến đường từ thành phố này đến thành phố khác.
Nhiệm vụ của bạn là tìm tất cả các thành phố trọng yếu từ Syrjälä đến Lehmälä.
Input
Output
Example
Test 1
Input
Output