HFAMOUS - Người nổi tiếng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

Công ty ABC chuyên thu thập thông tin về những người nổi tiếng. Trong hồ sơ của công ty có n người nổi tiếng được đánh số từ 1 đến n. Hồ sơ này chứa thông tin về m mối quan hệ, mỗi mối quan hệ được biểu diễn bằng hai số nguyên x, y cho biết rằng người nổi tiếng x quen với người nổi tiếng y và ngược lại.

 

Để tổ chức chương trình "Chung tay đón Tết" cho các em học sinh của mình, trường XYZ muốn mời một số người nổi tiếng trong danh sách của công ty ABC sao cho trong số những người được mời, người nào cũng quen với ít nhất k người khác và số lượng người được mời phải là nhiều nhất.

 

Input

Dòng thứ nhất chứa 3 số n <= 105, m <= 105, k <= n

Trong m dòng tiếp theo, mỗi dòng chứa 2 số nguyên x, y (1 <= x, y <= n)

 

Output

Dòng thứ nhất ghi số lượng người được mời, nếu không có cách mời, in ra 0

Nếu có cách mời, ghi chỉ số của từng người cách nhau bởi một khoảng trắng ở dòng thứ 2

 

Nếu có nhiều đáp án đúng, bạn chỉ cần in ra 1 đáp án bất kì

Ví dụ

  • input
    5 7 2
    4 3
    1 2
    4 1
    1 3
    3 2
    2 4
    5 4
    output
    4
    1 2 3 4

Giải thích ví dụ

Sơ đồ mối quan hệ có thể biểu diễn như sau

Vì người 1, 2, 3, 4 đều quen biết ít nhất 2 người, còn người 5 chỉ quen biết 1 người, nên chúng ta mời nhiều nhất là 4 người

Back to Top