Сипаттамасы
Кедергісі $1\,[\Omega]$ болатын резисторларды ғана пайдаланып, кедергісі $\sqrt{D}\,[\Omega]$ болатын резистор құрастырыңыз.
Сізге оң бүтін $D$ саны берілген. Төмендегі шарттардың барлығын қанағаттандыратын бір байланысқан бағытталмаған граф құрастырыңыз. Осы есептің шектеулерінде мұндай графтың әрқашан табылатынын дәлелдеуге болады.
- Төбелер саны $N$ мәні $2$ мен $300$ аралығында ($2$ мен $300$ қоса алғанда) болады және әрбір төбенің $1$-ден $N$-ге дейінгі әртүрлі нөмірі бар.
- Қырлар саны $M$ көп дегенде $300$ болады, ілмектерге (self-loops) және еселі қырларға (multiple edges) рұқсат етіледі.
- Төменде анықталған «$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