Chỉ sử dụng các điện trở có điện trở $1\,[\Omega]$, hãy xây dựng một điện trở có điện trở $\sqrt{D}\,[\Omega]$.

Bạn được cho một số nguyên dương $D$. Hãy xây dựng một đồ thị vô hướng liên thông thỏa mãn tất cả các điều kiện sau đây. Với các ràng buộc của bài toán này, có thể chứng minh rằng một đồ thị như vậy luôn tồn tại.

• Số lượng đỉnh $N$ nằm trong khoảng từ 2 đến 300, bao gồm cả 2 và 300, và mỗi đỉnh có nhãn phân biệt từ 1 đến $N$.
• Số lượng cạnh $M$ tối đa là 300, cho phép có khuyên và đa cạnh.
• "Điện trở tương đương từ đỉnh 1 đến đỉnh $N$", được định nghĩa như dưới đây, nằm trong sai số tuyệt đối $\pm 10^{-6}$ so với $\sqrt{D}$.

Cho $G$ là một đồ thị vô hướng liên thông với $n$ đỉnh và $m$ cạnh ($n \ge 2$), và giả sử cạnh thứ $j$ nối hai đỉnh $a_j, b_j$. Xét việc gán một số thực $V_i$ ($i = 1, 2, \dots, n$) cho mỗi đỉnh của đồ thị $G$, và một số thực $I_j$ ($j = 1, 2, \dots, m$) cho mỗi cạnh, sao cho tất cả các phương trình sau đây được thỏa mãn:

• $I_j = V_{a_j} - V_{b_j}$ ($j = 1, 2, \dots, m$)
• $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0$ ($i = 2, 3, \dots, n - 1$)
• $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

Có thể chứng minh rằng một cách gán như vậy luôn tồn tại, và hơn nữa giá trị $V_1 - V_n$ được xác định duy nhất. Chúng ta gọi giá trị này là "điện trở tương đương từ đỉnh 1 đến đỉnh $n$".

Dữ liệu vào

Dữ liệu vào gồm một số nguyên dương duy nhất $D$ ($1 \le D \le 5000$).

Dữ liệu ra

Trên dòng đầu tiên, in ra số lượng đỉnh $N$ và số lượng cạnh $M$ của đồ thị đã xây dựng, theo thứ tự này, cách nhau bởi dấu cách.

Trên mỗi dòng trong số $M$ dòng tiếp theo, dòng thứ $i$ ($i = 1, 2, \dots, M$) phải chứa hai đỉnh đầu mút của cạnh thứ $i$ được chọn, cách nhau bởi dấu cách.

Nếu có nhiều đồ thị thỏa mãn các điều kiện, bạn có thể in ra bất kỳ đồ thị nào trong số đó.

Ví dụ

Dữ liệu vào 1

1

Dữ liệu ra 1

4 5
1 2
1 3
2 3
2 4
3 4

Ghi chú

Hình minh họa dưới đây là kết quả đầu ra cho ví dụ đầu tiên.

Việc điện trở tương đương từ đỉnh 1 đến đỉnh $n$ bằng $1\,[\Omega]$ có thể được giải thích như sau:

• Vì tất cả các điện trở đều có điện trở $1\,[\Omega]$, và do tính đối xứng, điện thế tại đỉnh 2 và đỉnh 3 là bằng nhau, nên điện trở giữa chúng có thể được coi như không tồn tại.
• Kết quả là mạch điện rút gọn thành hai nhánh song song, mỗi nhánh gồm hai điện trở $1\,[\Omega]$ mắc nối tiếp.
• Điện trở tương đương của hai điện trở $1\,[\Omega]$ mắc nối tiếp là $2\,[\Omega]$, và điện trở tương đương của hai điện trở $2\,[\Omega]$ mắc song song là $1\,[\Omega]$.

Kết quả sau đây cũng được coi là đúng:

2 1
1 2