CSES - Critical Cities | Các thành phố quan trọng

Xem PDF

Điểm: 1900 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

\(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\)\(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\)\(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


  • 0
    Thanh72    3:30 p.m. 19 Tháng 8, 2023

    \(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

    • Dòng đầu tiên chứa hai số nguyên dương \(n(n \leq 10^5)\)\(m(m \leq 2 \times 10^5)\): 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\)\(b\) \((a, b \leq n)\): 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.

    Example

    Test 1

    Input
    5 5  
    1 2  
    2 3  
    2 4  
    3 5  
    4 5
    Output
    3
    1 2 5