Құндыздар мекендейтін, $0$-ден $N-1$-ге дейін нөмірленген $N$ арал бар. Бұл аралдар екі бағытты $N-1$ көпірмен байланысқан. Кейбір көпірлерді пайдаланып кез келген аралдар арасында қатынауға болады. Әрбір аралға тікелей қосылған көпірлер саны 18-ден аспайды. Әр аралда бір құндыз тұрады.

Кейде бірнеше құндыз жиналыс өткізу үшін бір аралға жиналады. Дәл үш құндыз кездескенде, олар келесі аралға жиналады:

Үш құндыз жиналған кезде жүріп өтетін көпірлердің жалпы санын барынша азайтатын арал (мұндай арал жалғыз болады).

Бұл арал үш құндыздың бірі тұратын аралмен сәйкес келуі мүмкін екенін ескеріңіз.

Сізді $N$ аралдың көпірлер арқылы қалай байланысқаны қызықтырады. Сіз аралдарға тікелей барып тексере алмайсыз, сондықтан құндыздарға бірнеше нұсқау бермекшісіз. Бір нұсқау келесідей болады:

• Сіз $u$, $v$ және $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$) үш аралын көрсетесіз де, $u$, $v$ және $w$ аралдарында тұратын құндыздарға жиналыс өткізуді тапсырасыз.
• Содан кейін сіз үш құндыздың қай аралға жиналғанын көре аласыз.

Сіз аз ғана нұсқау арқылы аралдардың қалай байланысқанын анықтағыңыз келеді.

Аралдар саны берілгенде, құндыздармен байланыса отырып, аралдардың қалай байланысқанын анықтайтын программа жазыңыз.

Іске асыру детальдары

Сіз бір файл жіберуіңіз керек.

Файлдың атауы — meetings.cpp. Ол келесі функцияны іске асыруы тиіс. Программа meetings.h файлын қосуы керек.

• void Solve(int N)

Бұл функция әр тест жағдайы үшін дәл бір рет шақырылады.

• N параметрі аралдар саны $N$-ді білдіреді.

Сіздің программаңыз келесі функцияларды шақыра алады.

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

Бұл функция сіз көрсеткен үш аралдың индекстері үшін сол жерде тұратын құндыздар жиналысқа жиналатын аралдың индексін қайтарады.

• Үш аралдың $u$, $v$ және $w$ индекстерін сәйкесінше u, v және 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$ шарттарын қанағаттандыруы тиіс. Әйтпесе сіздің программаңыз Wrong Answer [1] ретінде бағаланады.

• Query функциясы $100\,000$ реттен артық шақырылмауы тиіс. Әйтпесе сіздің программаңыз Wrong Answer [2] ретінде бағаланады.

• void Bridge(int u, int v)

Осы функцияны пайдаланып, сіз аралдардың көпірлер арқылы қалай байланысқанын жауап ретінде бересіз.

• u және v параметрлері $u$ мен $v$ аралдарының көпірмен тікелей байланысқанын білдіреді.
• Егер $0 \le u < v \le N-1$ шарты орындалмаса, сіздің программаңыз Wrong Answer [3] ретінде бағаланады.
• Егер $u$ және $v$ аралдары көпірмен тікелей байланыспаған болса, сіздің программаңыз Wrong Answer [4] ретінде бағаланады.
• Егер Bridge функциясы бірдей u және v параметрлерімен бірнеше рет шақырылса, сіздің программаңыз Wrong Answer [5] ретінде бағаланады.
• $N-1$ көпір болғандықтан, Bridge функциясы дәл $N-1$ рет шақырылуы тиіс. Егер Solve функциясының орындалуы аяқталған кезде Bridge функциясын шақыру саны $N-1$ болмаса, сіздің программаңыз Wrong Answer [6] ретінде бағаланады.

Маңызды ескертулер

• Сіздің программаңыз ішкі пайдалану үшін басқа функцияларды іске асыра алады немесе глобалды айнымалыларды пайдалана алады.
• Сіздің программаңыз стандартты енгізу мен стандартты шығаруды пайдаланбауы тиіс. Сіздің программаңыз ешқандай әдіспен басқа файлдармен байланыспауы тиіс. Бірақ программаңыз жөндеу (debugging) ақпаратын стандартты қателер ағынына (standard error) шығара алады.

Компиляция және тестілік іске қосу

Программаңызды тексеруге арналған үлгі грейдері бар архив файлын жарыс веб-бетінен жүктеп алуға болады. Архив файлында программаңыздың үлгі бастапқы коды да бар.

Үлгі грейдер — grader.cpp файлы. Программаңызды тексеру үшін grader.cpp, meetings.cpp және meetings.h файлдарын бір директорияға салып, программаларды компиляциялау үшін келесі команданы орындаңыз.

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

Компиляция сәтті аяқталғанда, grader орындалатын файлы жасалады.

Нақты грейдер үлгі грейдерден өзгеше екенін ескеріңіз. Үлгі грейдер стандартты енгізуден кіріс деректерді оқитын және нәтижелерді стандартты шығаруға жазатын бір процесс ретінде орындалады.

Үлгі грейдерге арналған кіріс деректер

Үлгі грейдер стандартты енгізуден келесі деректерді оқиды.

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

$A_i$ және $B_i$ ($0 \le i \le N-2$) $A_i$ және $B_i$ аралдарының көпірмен тікелей байланысқанын білдіреді.

Үлгі грейдердің шығыс деректері

Программа сәтті аяқталғанда, үлгі грейдер стандартты шығаруға келесі ақпаратты жазады (тырнақшалар түсінікті болу үшін берілген).

• Егер программаңыз дұрыс деп танылса, ол Query функциясын шақыру санын “Accepted: 100” түрінде жазады.
• Егер программаңыз Wrong Answer деп танылса, ол оның түрін “Wrong Answer [1]” ретінде жазады.

Егер сіздің программаңыз Wrong Answer қатесінің бірнеше түріне сәйкес келсе, үлгі грейдер олардың тек біреуін ғана хабарлайды.

Шектеулер

$A_i$ және $B_i$ анықтамасы үшін “Үлгі грейдерге арналған кіріс деректер” бөлімін қараңыз.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• Кейбір көпірлерді пайдаланып кез келген аралдар арасында қатынауға болады.
• Әрбір аралға тікелей қосылған көпірлер саны 18-ден аспайды.

Ішкі есептер

1. (7 ұпай) $N \le 7$.
2. (10 ұпай) $N \le 50$.
3. (12 ұпай) $N \le 300$.

4. (71 ұпай) Қосымша шектеулер жоқ.

5. 1, 2 және 3-ші ішкі есептер үшін, егер сіздің программаңыз ішкі есептің барлық тест жағдайларында дұрыс болса, сізге толық ұпай беріледі.

6. 4-ші ішкі есеп үшін, егер сіздің программаңыз барлық тест жағдайларында дұрыс болса, сіздің ұпайыңыз келесідей болады, мұндағы $X$ — бір тест жағдайында Query функциясын шақырудың ең көп саны:

   • егер $40\,000 < X \le 100\,000$ болса, 49 ұпай, және
   • егер $X \le 40\,000$ болса, 71 ұпай.

Өзара әрекеттесу мысалы

Мұнда үлгі грейдерге арналған кіріс деректер мысалы және соған сәйкес функция шақырулары берілген.

Кіріс деректер 1

5
0 1
0 2
1 3
1 4

Шақырулар мысалы