Информатикада NP-толық (NP-Complete, қысқаша NPC) есептер теориялық тереңдігі мен шешу қиындығын ұштастырған классикалық есептер класы болып табылады — қазіргі уақытқа дейін олардың полиномдық уақыттағы алгоритмі табылған жоқ, бірақ олардың кез келген біреуі шешілсе, барлық NP есептері оңай шешімін табады.

Алгоритмдерді зерттеуге құмар кішкентай W әрқашан NPC есептеріне шақыру тастауды армандайтын. Ол графтар теориясындағы әйгілі «Ең үлкен ортақ индукцияланған ішкі граф есебі» дәл осы классикалық NPC есебі екенін білді. Жалпы графтардағы еңсерілмейтін күрделілік шыңырауына тап болған кішкентай W бір қадам артқа шегініп, құрылымы әлдеқайда әсем ағаштардан бастап, ағаштардағы изоморфты байланысқан ішкі граф есебін зерттеуді ұйғарды.

Нақтырақ айтқанда, әрқайсысы $n$ төбеден тұратын түбірсіз екі $T_1$ және $T_2$ ағашы берілген, екі ағаштың да төбелері сәйкесінше $1 \sim n$ аралығында нөмірленген. Кішкентай W $T_1$ ағашынан бос емес $V_1$ төбелер ішкі жиынын және $T_2$ ағашынан бос емес $V_2$ төбелер ішкі жиынын таңдап, әр жиынның ішіндегі төбелер арасындағы бастапқы ағаштағы барлық қырларды сақтай отырып, сәйкесінше $G_1$ және $G_2$ екі ішкі графын индукциялап алғысы келеді.

Кішкентай W индукцияланған $G_1, G_2$ екі ішкі графының бір мезгілде келесі шарттарды қанағаттандыруын талап етеді:

1. Байланыстылық: $G_1$ де, $G_2$ де байланысқан графтар болып табылады (дербес жағдайда, тек $1$ ғана төбеден тұратын граф та байланысқан деп есептеледі).
2. Изоморфтылық: $G_1$ мен $G_2$ өзара изоморфты. Яғни, $V_1$ жиынынан $V_2$ жиынына $f : V_1 \to V_2$ биекциясы (өзара бірмәнді сәйкестік) табылып, кез келген $u, v \in V_1$ үшін $u$ мен $v$ төбелері $G_1$ графында қырмен жалғанған болуы тек және тек $f(u)$ мен $f(v)$ төбелері $G_2$ графында қырмен жалғанған болғанда ғана орындалады. Ескерту: өзара сәйкес келетін $u$ және $f(u)$ төбелерінің нөмірлері бірдей болуы міндетті емес.

Енді кішкентай W осы жеңілдетілген есепті сізге тапсырды: жоғарыдағы талаптарды қанағаттандыратын изоморфты байланысқан ішкі графтарда ең көп дегенде қанша төбе болуы мүмкін екенін есептеңіз (яғни $|V_1|$ шамасының ең үлкен мәнін табыңыз)?

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

Деректер stdin-нен оқылады.

Бірінші жолда әр ағаштағы төбелер санын білдіретін бір оң бүтін $n$ саны берілген.

Келесі $n - 1$ жолдың әрқайсысында $T_1$ ағашындағы бағытталмаған $(u, v)$ қырын білдіретін екі оң бүтін $u, v$ сандары берілген.

Келесі $n - 1$ жолдың әрқайсысында $T_2$ ағашындағы бағытталмаған $(u, v)$ қырын білдіретін екі оң бүтін $u, v$ сандары берілген.

Шығыс деректер

Нәтижені stdout-қа шығарыңыз.

Таңдалған изоморфты байланысқан ішкі графтардың ең үлкен төбелер санын білдіретін бір оң бүтін санды бір жолға шығарыңыз.

Мысалдар

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

4
1 2
2 3
3 4
1 2
1 3
1 4

Шығыс деректер 1

3

Түсініктеме

$T_1$ ағашында $V_1 = \{1, 2, 3\}$ төбелер жиынын, ал $T_2$ ағашында $V_2 = \{1, 2, 3\}$ төбелер жиынын таңдайық. $V_1$ жиынындағы $1, 2, 3$ төбелерін ретімен $V_2$ жиынындағы $2, 1, 3$ төбелеріне сәйкестендірсек, индукцияланған екі ішкі граф та $3$ төбеден тұратын тізбек болады, яғни байланыстылық пен изоморфтылық шарттарын қанағаттандырады.

$T_1$ өзі тізбек болғандықтан, оның кез келген байланысқан ішкі графы да міндетті түрде тізбек болады; ал жұлдызша граф $T_2$ ішіндегі ең ұзын тізбек тек $3$ төбеден тұрады, сондықтан төбелер саны $3$-тен асатын изоморфты байланысқан ішкі графты таңдау мүмкін емес.

Мысал 2

Қатысушы директориясындағы npc/npc2.in және npc/npc2.ans файлдарын қараңыз.

Бұл мысал $1$-ішкі есептің шектеулерін қанағаттандырады.

Мысал 3

Қатысушы директориясындағы npc/npc3.in және npc/npc3.ans файлдарын қараңыз.

Бұл мысал $4$-ішкі есептің шектеулерін қанағаттандырады.

Мысал 4

Қатысушы директориясындағы npc/npc4.in және npc/npc4.ans файлдарын қараңыз.

Бұл мысал $7$-ішкі есептің шектеулерін қанағаттандырады.

Ішкі есептер

Барлық деректер үшін $1 \le n \le 500$ екендігіне, әр қырдың екі шеткі төбесінің нөмірлері $1 \sim n$ аралығында болатынына және берілген екі графтың да дұрыс ағаш екендігіне кепілдік беріледі.

Бұл есептің толық ұпайы — $150$ ұпай, ішкі есептер бойынша топтастырып тексеру қолданылады. Тек ішкі есептегі барлық тесттерден өткенде ғана сол ішкі есептің ұпайы беріледі. Әр ішкі есептің нақты деректер ауқымы төмендегі кестеде көрсетілген.

A ерекше қасиеті: Екі ағаштағы барлық төбелердің дәрежесі $3$-тен аспайды.

B ерекше қасиеті: Изоморфты бейнелеуі $T_1$ ағашының $1$-төбесін $T_2$ ағашының $1$-төбесіне сәйкестендіретін оңтайлы шешім бар.

C ерекше қасиеті: Соңғы жауап $n - 1$ мәнінен кем емес екендігіне кепілдік беріледі.

Ескерту: Ағаштағы төбенің дәрежесі деп сол төбемен тікелей жалғанған қырлардың санын айтады.