Đa giác

Điểm: 200

Thời gian: 1.0s

Bộ nhớ: 256M

Input: POLYGON.INP

Output: POLYGON.OUT

Tác giả:

haiender288

Dạng bài

Cho đa giác lồi gồm $n$ đỉnh và $m$ đường chéo. Biết rằng nếu hai đường chéo khác nhau chỉ có thể gặp nhau tại đỉnh của đa giác. Các đỉnh của đa giác được đánh số từ 1 tới $n$ theo một hoán vị nào đó.
Yêu cầu: Cho biết danh sách $n$ cạnh và $m$ đường chéo, hãy liệt kê các đỉnh của đa giác theo đúng thứ tự tạo thành đa giác đã cho.

Input, Output

Input: (POLYGON.inp)

Dòng 1 chứa hai số nguyên không âm $n, m\leq 10^5$ ( $n\geq 3$ ).
$n+m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $i, j$ cho biết có đường chéo hoặc cạnh nối từ đỉnh $i$ tới đỉnh $j$ .

Output: (POLYGON.out)

Ghi ra một dòng liệt kê dãy các đỉnh của đa giác. Bởi có nhiều cách liệt kê đỉnh xác định đa giác đã cho, cần đưa ra dãy có thứ tự từ điển nhỏ nhất

Sample

Input (POLYGON.inp)

Output (POLYGON.out)

1 3 2 4

Bình luận đầu tiên

Bình luận

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