Beskrivning
Med hjälp av enbart resistorer med resistansen $1\,[\Omega]$, konstruera en resistor med resistansen $\sqrt{D}\,[\Omega]$.
Du får ett positivt heltal $D$. Konstruera en sammanhängande oriktad graf som uppfyller alla följande villkor. Under begränsningarna i detta problem kan det bevisas att en sådan graf alltid existerar.
- Antalet hörn $N$ är mellan $2$ och $300$ ($2$ och $300$ inklusive), och varje hörn har en unik etikett från $1$ till $N$.
- Antalet kanter $M$ är högst $300$, och öglor (self-loops) samt multipelkanter är tillåtna.
- Den "effektiva resistansen från hörn $1$ till hörn $N$", definierad nedan, ligger inom ett absolut fel på $\pm 10^{-6}$ från $\sqrt{D}$.
Låt $G$ vara en sammanhängande oriktad graf med $n$ hörn och $m$ kanter ($n \ge 2$), och anta att den $j$-te kanten förbinder hörnen $a_j, b_j$. Betrakta att tilldela ett reellt tal $V_i$ ($i = 1, 2, \dots, n$) till varje hörn i grafen $G$, och ett reellt tal $I_j$ ($j = 1, 2, \dots, m$) till varje kant, så att alla följande ekvationer är uppfyllda:
- $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$
Det kan bevisas att en sådan tilldelning alltid existerar, och dessutom att värdet på $V_1 - V_n$ är entydigt bestämt. Vi definierar detta värde som den "effektiva resistansen från hörn $1$ till hörn $n$".
Indata
Indata består av ett enda positivt heltal $D$. ($1 \le D \le 5000$)
Utdata
På den första raden, skriv ut antalet hörn $N$ och antalet kanter $M$ i den konstruerade grafen, i denna ordning, separerade med mellanslag.
På var och en av de följande $M$ raderna ska den $i$-te raden ($i = 1, 2, \dots, M$) innehålla de två ändpunkterna för den $i$-te kanten, separerade med ett mellanslag.
Om det finns flera grafer som uppfyller villkoren kan vilken som helst av dem skrivas ut.
Exempel
Indata 1
1
Utdata 1
4 5 1 2 1 3 2 3 2 4 3 4
Anmärkning
Följande är en illustration av utdata för Exempel 1.
Att den effektiva resistansen från hörn $1$ till hörn $n$ är $1\,[\Omega]$ kan förklaras på följande sätt:
- Eftersom alla resistorer har resistansen $1\,[\Omega]$, och potentialerna vid hörnen $2$ och $3$ på grund av symmetri är lika, kan resistorn mellan dem behandlas som om den inte existerar.
- Som ett resultat reduceras kretsen till två parallella grenar, där varje gren består av två seriekopplade $1\,[\Omega]$-resistorer.
- Den effektiva resistansen för två seriekopplade $1\,[\Omega]$-resistorer är $2\,[\Omega]$, och den effektiva resistansen för två parallellkopplade $2\,[\Omega]$-resistorer är $1\,[\Omega]$.
Följande utdata betraktas också som korrekt:
2 1 1 2