Það eru $N$ eyjar þar sem bifrar búa, númeraðar frá $0$ til $N-1$. Þessar eyjar eru tengdar saman með $N-1$ tvístefnu brúm. Hægt er að ferðast á milli hvaða eyja sem er með því að nota einhverjar brýr. Fyrir hverja eyju eru í mesta lagi 18 brýr beintengdar við hana. Á hverri eyju býr einn bifur.

Stundum safnast nokkrir bifrar saman á eyju til að halda fund. Þegar nákvæmlega þrír bifrar hittast safnast þeir saman á eftirfarandi eyju:

Eyjunni sem lágmarkar heildarfjölda brúa sem bifrarnir þrír ferðast yfir þegar þeir safnast saman (slík eyja er til og er ótvírætt ákvörðuð).

Athugið að þessi eyja getur fallið saman við eyju þar sem einn af bifrunum þremur býr.

Þú hefur áhuga á því hvernig eyjarnar $N$ eru tengdar saman með brúm. Þú getur ekki farið og athugað eyjarnar beint, svo þú ætlar að gefa bifrunum nokkrarskipanir. Ein skipun er sem hér segir:

• Þú tilgreinir þrjár eyjar $u$, $v$ og $w$ ($0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, $v \ne w$), og lætur bifrana sem búa á eyjunum $u$, $v$ og $w$ halda fund.
• Þá getur þú séð á hvaða eyju bifrarnir þrír safnast saman.

Þú vilt ákvarða hvernig eyjarnar eru tengdar með fáum skipunum.

Skrifaðu forrit sem, þegar gefinn er fjöldi eyja, í samskiptum við bifrana, ákvarðar hvernig eyjarnar eru tengdar.

Útfærsluatriði

Þú þarft að skila einni skrá.

Nafn skrárinnar er meetings.cpp. Hún á að útfæra eftirfarandi fall. Forritið á að innihalda meetings.h.

• void Solve(int N)

Þetta fall er kallað nákvæmlega einu sinni fyrir hvert prófunartilvik.

• Viðfangið N táknar $N$, fjölda eyja.

Forritið þitt getur kallað á eftirfarandi föll.

• int Query(int u, int v, int w)

Þetta fall skilar, fyrir númer þriggja eyja sem þú tilgreinir, númeri eyjunnar þar sem bifrarnir sem búa þar safnast saman á fund.

• Þú tilgreinir númerin $u$, $v$ og $w$ á eyjunum þremur með viðföngunum u, v og w, í þessari röð. Þau verða að uppfylla $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ og $v \ne w$. Annars telst forritið þitt vera Wrong Answer [1].

• Ekki má kalla á fallið Query oftar en $100\,000$ sinnum. Annars telst forritið þitt vera Wrong Answer [2].

• void Bridge(int u, int v)

Með því að nota þetta fall svarar þú því hvernig eyjarnar eru tengdar með brúm.

• Viðföngin u og v tákna að eyjarnar $u$ og $v$ séu beintengdar með brú.
• Ef $0 \le u < v \le N-1$ gildir ekki telst forritið þitt vera Wrong Answer [3].
• Ef eyjarnar $u$ og $v$ eru ekki beintengdar með brú telst forritið þitt vera Wrong Answer [4].
• Ef kallað er á fallið Bridge með sömu viðföngum u og v oftar en einu sinni telst forritið þitt vera Wrong Answer [5].
• Þar sem það eru $N-1$ brýr verður að kalla á fallið Bridge nákvæmlega $N-1$ sinnum. Ef fjöldi kalla á fallið Bridge er ekki $N-1$ í lok keyrslu fallsins Solve telst forritið þitt vera Wrong Answer [6].

Mikilvægar athugasemdir

• Forritið þitt getur útfært önnur föll til innri nota eða notað víðværar breytur.
• Forritið þitt á ekki að nota staðalinntak né staðalúttak. Forritið þitt á ekki að eiga samskipti við aðrar skrár með neinum hætti. Hins vegar má forritið þitt skrifa aflúsunarupplýsingar á staðalvilluúttak (standard error).

Þýðing og prófunarkeyrsla

Þú getur sótt safnskrá af vefsíðu keppninnar sem inniheldur dæmatékkarann til að prófa forritið þitt. Safnskráin inniheldur einnig sýnishorn af frumkóðaskrá fyrir forritið þitt.

Dæmatékkarinn er skráin grader.cpp. Til að prófa forritið þitt skaltu setja grader.cpp, meetings.cpp og meetings.h í sömu möppu og keyra eftirfarandi skipun til að þýða forritin þín.

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

Þegar þýðingin tekst verður keyranlega skráin grader búin til.

Athugaðu að raunverulegi tékkarinn er ólíkur dæmatékkaranum. Dæmatékkarinn verður keyrður sem eitt ferli sem les inntaksgögn af staðalinntaki og skrifar niðurstöðurnar á staðalúttak.

Inntak fyrir dæmatékkarann

Dæmatékkarinn les eftirfarandi gögn af staðalinntaki.

$$ \begin{array}{ll} N & \\ A_0 & B_0 \\ \vdots & \\ A_{N-2} & B_{N-2} \end{array} $$

$A_i$ og $B_i$ ($0 \le i \le N-2$) tákna að eyjarnar $A_i$ og $B_i$ séu beintengdar með brú.

Úttak fyrir dæmatékkarann

Þegar forritið lýkur keyrslu eðlilega skrifar dæmatékkarinn eftirfarandi upplýsingar á staðalúttak (gæsalappir eru til skýringar).

• Ef forritið þitt telst rétt skrifar hann fjölda kalla á fallið Query sem “Accepted: 100”.
• Ef forritið þitt telst vera Wrong Answer skrifar hann tegund villunnar sem “Wrong Answer [1]”.

Ef forritið þitt fellur undir margar tegundir af Wrong Answer tilkynnir dæmatékkarinn aðeins eina þeirra.

Takmarkanir

Sjá kaflann “Inntak fyrir dæmatékkarann” fyrir skilgreiningu á $A_i$ og $B_i$.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• Hægt er að ferðast á milli hvaða eyja sem er með því að nota einhverjar brýr.
• Fyrir hverja eyju eru í mesta lagi 18 brýr beintengdar við hana.

Undirverkefni

1. (7 stig) $N \le 7$.
2. (10 stig) $N \le 50$.
3. (12 stig) $N \le 300$.

4. (71 stig) Engar frekari takmarkanir.

5. Fyrir undirverkefni 1, 2 og 3 færðu fullt hús stiga ef forritið þitt er rétt fyrir öll prófunartilvik í undirverkefninu.

6. Fyrir undirverkefni 4, ef forritið þitt er rétt fyrir öll prófunartilvik, verða stigin þín sem hér segir, þar sem $X$ er hámarksfjöldi kalla á fallið Query í prófunartilviki:

   • 49 stig ef $40\,000 < X \le 100\,000$, og
   • 71 stig ef $X \le 40\,000$.

Dæmi um samskipti

Hér er dæmi um inntak fyrir dæmatékkarann og samsvarandi fallaköll.

Inntak 1

5
0 1
0 2
1 3
1 4

Dæmi um köll