Trong quá trình tạo dữ liệu cho bài toán D: ㄷㄷㄷㅈ, ban giám khảo UCPC nhận thấy rằng việc tạo ra một cây DUDUDUNGA với nhiều đỉnh là một việc khó khăn. Cho trước $N$, hãy viết chương trình xuất ra một cây DUDUDUNGA có $N$ đỉnh.

Dữ liệu vào

Dòng đầu tiên chứa số lượng đỉnh của cây $N$. ($6 \le N \le 300\,000$)

Dữ liệu ra

Xuất ra $N-1$ dòng, mỗi dòng chứa hai đầu mút của một cạnh, cách nhau bởi dấu cách. Số hiệu của các đỉnh phải là các số nguyên từ $1$ đến $N$.

Ví dụ

Dữ liệu vào 1

6

Dữ liệu ra 1

1 2
2 3
3 4
4 5
4 6

Ghi chú

Định nghĩa về cây DUDUDUNGA có thể tham khảo trong bài toán D: ㄷㄷㄷㅈ. Với mọi $N$ được cho trong dữ liệu vào, luôn tồn tại một cây DUDUDUNGA có đúng $N$ đỉnh.