Một công ty điện thoại di động đưa ra chương trình khuyến mãi sau: mỗi khách hàng mới được chọn đúng $k$ số điện thoại khác và tất cả các cuộc gọi giữa khách hàng đó với bất kỳ ai trong số $k$ liên hệ đã chọn đều miễn phí (theo cả hai chiều).
Một nhóm gồm $n$ học sinh (được đánh số từ $1$ đến $n$) muốn tận dụng chương trình khuyến mãi này. Mỗi học sinh $i$ phải chọn đúng $k$ liên hệ phân biệt từ tập hợp $\{1, 2, \dots, n\} \setminus \{i\}$.
Ta nói rằng hai học sinh $i$ và $j$ có thể nói chuyện miễn phí nếu ít nhất một trong hai điều kiện sau được thỏa mãn:
- $i$ đã chọn $j$ làm một trong các liên hệ miễn phí, hoặc
- $j$ đã chọn $i$ làm một trong các liên hệ miễn phí.
Các học sinh muốn chọn các liên hệ miễn phí sao cho bất kỳ học sinh nào cũng có thể nói chuyện miễn phí với bất kỳ học sinh nào khác, tức là với mọi cặp $(i, j)$ thỏa mãn $1 \le i < j \le n$, hai học sinh $i$ và $j$ đều có thể nói chuyện miễn phí.
Với số $k$ cho trước, nhiệm vụ của bạn là:
- xác định số lượng học sinh tối đa $n$ mà cấu hình như vậy có thể thực hiện được,
- xây dựng một cấu hình chọn liên hệ hợp lệ cho giá trị $n$ tối đa này.
Dữ liệu vào
Dữ liệu vào gồm một số nguyên duy nhất $k$.
Dữ liệu ra
Trên dòng đầu tiên, in ra một số nguyên duy nhất $n$ — số lượng học sinh tối đa có thể chọn các liên hệ miễn phí sao cho hai học sinh bất kỳ đều có thể nói chuyện miễn phí với nhau.
Trên $n$ dòng tiếp theo, in ra $k$ liên hệ miễn phí được chọn bởi mỗi học sinh: trên dòng $i+1$ (với $1 \le i \le n$), in ra $k$ số nguyên phân biệt $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Mỗi $a_{i,j}$ phải thỏa mãn $1 \le a_{i,j} \le n$ và $a_{i,j} \neq i$. Các dòng này cho biết học sinh $i$ đã chọn các học sinh $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ làm liên hệ miễn phí của mình.
Nếu có nhiều đáp án hợp lệ, hãy in ra một đáp án bất kỳ.
Giới hạn
- $1 \le k \le 1000$.
Ví dụ 1
2
5
2 5
3 4
1 5
1 3
2 4
Ghi chú
Trong ví dụ, $k = 2$ và số lượng học sinh tối đa có thể chọn các liên hệ miễn phí sao cho hai học sinh bất kỳ có thể nói chuyện với nhau miễn phí là $n = 5$. Với mỗi cặp học sinh phân biệt, ít nhất một người đã chọn người kia, vì vậy hai người bất kỳ đều có thể nói chuyện miễn phí.