Centre for Gifted Education - Hanoi university of Technology

Tìm kiếm ưu tiên chiều rộng hay tìm kiếm theo chiều rộng (tiếng Anh: Breadth-first search - BFS) là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.

Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển theo nguyên tắc: gần trước xa sau.

Ví dụ:

Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh A, đi theo cạnh trái, tiếp tục tìm kiếm xong ở cây con trái mới chuyển sang tìm kiếm ở cây con phải. Thứ tự thăm viếng các đỉnh là: A, B, C, E, D, F, G.

Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh A, vì B chưa được thăm nên theo cạnh AB ta thăm B, sau đó ta quay lại A thăm tiếp C, rồi quay lại A thăm tiếp E. Đã hết đỉnh kề với A, ta đi đến B thăm đỉnh D, quay lại B thăm tiếp đỉnh F. Hết đỉnh kề với B ta quay lại B rồi quay lại A, sau đó đến C và thăm tiếp đỉnh G.

Bài toán đặt ra là:

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m.

Bằng thuật toán tìm kiếm theo chiều rộng, hãy đưa ra danh sách các đỉnh theo thứ tự tìm kiếm. Biết rằng: Đỉnh nào có chỉ số bé hơn sẽ được ưu tiên thăm trước.

Input

Dòng 1: Ghi 2 số nguyên n, m M dòng tiếp theo: Mỗi dòng gồm 2 số nguyên i, j mô tả 1 cạnh

Output

Gồm N dòng; Mỗi dòng gồm 1 số ghi số hiệu đỉnh theo thứ tự BFS.

Example

Input:
7 7
1 2
1 3
1 5
2 4
2 6
3 7
5 6

Output:
1
2
3
5
4
6
7

Giới hạn:
1 <= n <= 100
1 <= m <=n(n-1)/2