一家行動電信公司推出了以下促銷活動:每位新客戶可以選擇恰好 $k$ 個其他電話號碼,該客戶與所選的 $k$ 位聯絡人中任何一位之間的所有通話均為免費(雙向皆免費)。
有一群共 $n$ 位學生(編號從 $1$ 到 $n$)想要利用這項促銷活動。每位學生 $i$ 必須從集合 $\{1, 2, \dots, n\} \setminus \{i\}$ 中選擇恰好 $k$ 位互不相同的聯絡人。
若滿足以下至少一項條件,我們就稱兩位學生 $i$ 與 $j$ 可以免費通話:
- $i$ 選擇了 $j$ 作為其中一位免費聯絡人,或者
- $j$ 選擇了 $i$ 作為其中一位免費聯絡人。
學生們希望妥善選擇各自的免費聯絡人,使得任意一位學生都能與任意另一位學生免費通話,亦即對於每一對滿足 $1 \le i < j \le n$ 的 $(i, j)$,學生 $i$ 與 $j$ 皆可免費通話。
對於給定的 $k$,你的任務是:
- 確定能達成此配置的學生最大可能數量 $n$,
- 為此最大的 $n$ 構造出一組合法的聯絡人選擇配置。
輸入格式
輸入包含一個整數 $k$。
輸出格式
在第一行輸出一個整數 $n$ —— 能選擇免費聯絡人使得任意兩位學生皆可互相免費通話的最大學生人數。
在接下來的 $n$ 行,輸出每位學生所選的 $k$ 位免費聯絡人:在第 $i+1$ 行(對於 $1 \le i \le n$),輸出 $k$ 個互不相同的整數 $a_{i,1}, a_{i,2}, \dots, a_{i,k}$。每個 $a_{i,j}$ 必須滿足 $1 \le a_{i,j} \le n$ 且 $a_{i,j} \neq i$。這些行表示學生 $i$ 選擇了學生 $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ 作為其免費聯絡人。
若有多組合法答案,輸出任意一組即可。
數據範圍
- $1 \le k \le 1000$.
範例 1
2
5
2 5
3 4
1 5
1 3
2 4
範例說明
在範例中,$k = 2$,能選擇免費聯絡人使得任意兩位學生皆可互相免費通話的最大學生人數為 $n = 5$。對於每一對相異的學生,至少有一方選擇了另一方,因此任意兩人皆可免費通話。