CJ đi thăm người quen

Xem PDF

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

Một ngày, CJ cảm thấy lâu rồi chưa tới chơi nhà của tất cả các người quen của mình ở vùng Los Santos, nên đã quyết định đi dạo quanh, thăm tất cả người quen trong vùng, rồi trở lại tiếp tục công việc của mình.

Vùng Los Santos có \(N\) ngôi nhà có người quen, đánh số từ \(1\) tới \(N\), và \(M\) con đường hai chiều, giữa hai ngôi nhà có không quá một con đường nối trực tiếp. CJ còn khá nhiều việc chưa giải quyết nên xuất phát từ một ngôi nhà, đi qua hết tất cả ngôi nhà còn lại, mỗi ngôi nhà tới đúng một lần, và trở về ngôi nhà xuất phát (không ngôi nhà nào đi hai lần trừ ngôi nhà xuất phát, không bỏ qua ngôi nhà nào).

Yêu cầu: Biết rằng tồn tại ít nhất một hành trình như vậy. Hãy chỉ ra cho CJ một hành trình trên.

Input

  • Gồm \(M + 1\) dòng:
  • Dòng đầu tiên chứa hai số nguyên dương \(N\), \(M\) thể hiện số ngôi nhà có người quen và số con đường hai chiều \((M \leq \dfrac{N . (N-1)}{2})\).
  • \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\)\(v_i\) thể hiện có đường hai chiều nối hai ngôi nhà \(u_i\)\(v_i\) và \(u_i \neq v_i\)

Output

  • Ghi ra \(N + 1\) số là số hiệu của các ngôi nhà theo thứ tự hành trình trên một dòng.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \leq 30\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N \leq 2.10^3\)
  • Subtask \(3\) (\(20\%\) số điểm): \(N \leq 4.10^3\)
    (Đẩy giới hạn test cao hơn cho có màu :V)

Test 1

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

Bình luận


  • 0
    BeTapDi    7:43 a.m. 15 Tháng 7, 2020

    Giới hạn chuẩn là bnh vậy a chứ e ms biết chạy đến n = 20 à 🙂


    • 0
      hhoangcpascal    9:32 a.m. 15 Tháng 7, 2020

      thì là như đề. 4.10^3


      • 0
        WuTan    3:49 p.m. 15 Tháng 7, 2020

        sợ hãi sợ hãi

      1 bình luận nữa