CSES - Longest Flight Route | Lộ trình bay dài nhất

Xem PDF

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

Uolevi đã giành chiến thắng trong một cuộc thi, và giải thưởng là một chuyến bay miễn phí mà có thể bao gồm một hoặc nhiều chuyến bay qua các thành phố. Tất nhiên, Uolevi muốn chọn một chuyến đi có nhiều thành phố nhất có thể.

Uolevi muốn bay từ Syrjälä đến Lehmälä để anh thăm số lượng thành phố tối đa. Bạn được cho danh sách các chuyến bay khả thi, và bạn biết rằng không có chu trình có hướng trong mạng lưới chuyến bay.

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\)\(m\): số lượng thành phố và chuyến bay. Các thành phố được đánh số \(1,2,\ldots,n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
  • Sau này, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có hai số nguyên \(a\)\(b\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Mỗi chuyến bay là một chuyến bay một chiều.

Output

  • Đầu tiên in số lượng thành phố tối đa trong lộ trình. Sau này, in các thành phố theo thứ tự mà chúng sẽ được thăm. Bạn có thể in bất kì giải pháp hợp lệ nào.
  • Nếu không có lời giải nào, in IMPOSSIBLE.

Constraints

  • \(2 \leq n \leq 10 ^ 5\)
  • \(1 \leq m \leq 2 \cdot 10 ^ 5\)
  • \(1 \leq a, b \leq n\)

Example

Sample input

5 5
1 2
2 5
1 3
3 4
4 5

Sample output

4
1 3 4 5


Bình luận

Không có bình luận nào.