Cho một cây gồm n đỉnh đánh số từ 1, 2, ...n và n-1 cạnh hai chiều nối các đỉnh.

Nhiệm vụ của bạn là cho biết thứ tự duyệt theo tìm kiếm chiều rộng từ đỉnh 1.

*Lưu ý: * Thứ tự được sắp sếp theo thứ tự nhập vào của các cạnh. Tức là u sẽ thăm trước v khi u được nhập trước v.

Input

Dòng đầu tiên gồm số n (~ 2 \le n \le 2.10^5 ~) - số đỉnh của cây.

N-1 dòng tiếp theo gồm 2 số u và v (~ 1 \le u, v \le n ~) - có cạnh hai chiều nối từ đỉnh u đến đỉnh v.

Output

Thứ tự duyệt theo tìm kiếm chiều rộng từ đỉnh 1 (theo thứ tự nhập vào)

Examples

Input 1

7
1 6
1 4
4 2
2 5
4 3
3 7

Output 1

1 6 4 2 3 5 7