題目描述
只係用電阻為 $1\,[\Omega]$ 嘅電阻器,構造一個電阻為 $\sqrt{D}\,[\Omega]$ 嘅電阻器。
俾定一個正整數 $D$。請構造一個滿足以下所有條件嘅連通無向圖。喺題目俾定嘅約束之下,可以證明咁樣嘅圖一定存在。
- 頂點數 $N$ 喺 $2$ 到 $300$ 之間(包含 $2$ 同 $300$),每個頂點都有由 $1$ 到 $N$ 嘅唔同編號。
- 邊數 $M$ 最多係 $300$,允許存在自環同重邊。
- 「由頂點 $1$ 到頂點 $N$ 嘅等效電阻」(定義如下)同 $\sqrt{D}$ 嘅絕對誤差喺 $\pm 10^{-6}$ 以內。
設 $G$ 係一個有 $n$ 個頂點同 $m$ 條邊嘅連通無向圖($n \ge 2$),假設第 $j$ 條邊連接頂點 $a_j, b_j$。考慮為圖 $G$ 嘅每個頂點分配一個實數 $V_i$($i = 1, 2, \dots, n$),同埋為每條邊分配一個實數 $I_j$($j = 1, 2, \dots, m$),令以下所有方程成立:
- $I_j = V_{a_j} - V_{b_j} \quad (j = 1, 2, \dots, m)$
- $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0 \quad (i = 2, 3, \dots, n - 1)$
- $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$
可以證明咁樣嘅賦值一定存在,而且 $V_1 - V_n$ 嘅值係唯一確定嘅。我哋將呢個值定義為「由頂點 $1$ 到頂點 $n$ 嘅等效電阻」。
輸入格式
輸入為一個正整數 $D$。($1 \le D \le 5000$)
輸出格式
第一行輸出構造出嚟嘅圖嘅頂點數 $N$ 同邊數 $M$,用空格隔開。
接住落嚟嘅 $M$ 行入面,第 $i$ 行($i = 1, 2, \dots, M$)應該包含第 $i$ 條邊嘅兩個端點,用空格隔開。
如果存在多個滿足條件嘅圖,輸出其中任何一個就得。
範例
範例輸入 1
1
範例輸出 1
4 5 1 2 1 3 2 3 2 4 3 4
備註
以下係範例 1 輸出嘅示意圖。
由頂點 $1$ 到頂點 $n$ 嘅等效電阻係 $1\,[\Omega]$,解釋如下:
- 因為所有電阻器嘅電阻都係 $1\,[\Omega]$,而且根據對稱性,頂點 $2$ 同 $3$ 嘅電勢相等,所以佢哋之間嘅電阻器可以當做唔存在。
- 結果電路簡化為兩個並聯嘅分支,每個分支由兩個串聯嘅 $1\,[\Omega]$ 電阻器組成。
- 兩個 $1\,[\Omega]$ 電阻器串聯嘅等效電阻係 $2\,[\Omega]$,兩個 $2\,[\Omega]$ 電阻器並聯嘅等效電阻係 $1\,[\Omega]$。
以下輸出亦都被視為正確:
2 1 1 2