間流動電話公司推出咗以下優惠活動:每位新客戶可以揀啱啱好 $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$。對於每一對唔同嘅學生,至少有一個人揀咗對方,所以任意兩個人都可以免費通話。