Deskripsi
Dengan hanya menggunakan resistor berhambatan $1\,[\Omega]$, buatlah sebuah resistor dengan hambatan $\sqrt{D}\,[\Omega]$.
Diberikan sebuah bilangan bulat positif $D$. Buatlah satu graf tak berarah terhubung yang memenuhi semua syarat berikut. Di bawah batasan masalah ini, dapat dibuktikan bahwa graf seperti itu selalu ada.
- Banyaknya simpul $N$ berada di antara $2$ dan $300$ ($2$ dan $300$ inklusif), dan setiap simpul memiliki label berbeda dari $1$ hingga $N$.
- Banyaknya sisi $M$ paling banyak adalah $300$, serta loop diri (self-loop) dan sisi ganda (multiple edges) diperbolehkan.
- "Hambatan efektif dari simpul $1$ ke simpul $N$", yang didefinisikan di bawah ini, berada dalam galat mutlak $\pm 10^{-6}$ dari $\sqrt{D}$.
Misalkan $G$ adalah graf tak berarah terhubung dengan $n$ simpul dan $m$ sisi ($n \ge 2$), dan misalkan sisi ke-$j$ menghubungkan simpul $a_j, b_j$. Tinjau pemberian sebuah bilangan riil $V_i$ ($i = 1, 2, \dots, n$) pada setiap simpul dari graf $G$, dan sebuah bilangan riil $I_j$ ($j = 1, 2, \dots, m$) pada setiap sisi, sehingga semua persamaan berikut terpenuhi:
- $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$
Dapat dibuktikan bahwa pemberian nilai seperti itu selalu ada, dan nilai $V_1 - V_n$ ditentukan secara tunggal. Kita mendefinisikan nilai ini sebagai "hambatan efektif dari simpul $1$ ke simpul $n$".
Masukan
Masukan terdiri dari satu bilangan bulat positif $D$. ($1 \le D \le 5000$)
Keluaran
Pada baris pertama, cetak banyaknya simpul $N$ dan banyaknya sisi $M$ dari graf yang dibuat, sesuai urutan tersebut, dipisahkan oleh spasi.
Pada masing-masing dari $M$ baris berikutnya, baris ke-$i$ ($i = 1, 2, \dots, M$) harus berisi dua titik ujung dari sisi ke-$i$, dipisahkan oleh spasi.
Jika terdapat beberapa graf yang memenuhi syarat, Anda boleh mencetak yang mana saja.
Contoh
Masukan 1
1
Keluaran 1
4 5 1 2 1 3 2 3 2 4 3 4
Catatan
Berikut adalah ilustrasi keluaran untuk Contoh 1.
Bahwa hambatan efektif dari simpul $1$ ke simpul $n$ adalah $1\,[\Omega]$ dapat dijelaskan sebagai berikut:
- Karena semua resistor memiliki hambatan $1\,[\Omega]$, dan berdasarkan simetri potensial pada simpul $2$ dan $3$ adalah sama, maka resistor di antara keduanya dapat dianggap tidak ada.
- Akibatnya, rangkaian dapat disederhanakan menjadi dua cabang paralel, dengan masing-masing cabang terdiri dari dua resistor $1\,[\Omega]$ yang disusun seri.
- Hambatan efektif dari dua resistor $1\,[\Omega]$ yang disusun seri adalah $2\,[\Omega]$, dan hambatan efektif dari dua resistor $2\,[\Omega]$ yang disusun paralel adalah $1\,[\Omega]$.
Keluaran berikut juga dianggap benar:
2 1 1 2