SPOJ in Armenian

Նախքան Ալադինի արկածները սկսելը՝ նա տարբեր գույնի քարերի սիրահար էր: Մի անգամ նա
հայտնվել էր երկու կախարդական քարանձավների մոտ որոնցում կային բազմապիսի քարեր: Նրա
նպատակն էր վերցնել ինչքան հնարավոր է շատ քարեր, բայց քանի որ քարանձավը
կախարդական էր, նա պետք է ենթարկվեր որոշ կանոնների: Քարանձավներից յուրաքանչյուրը
բավարարում էր հետևյալ պայմաններին: Քարանձավը ունի ճիշտ մեկ մուտք: Քարանձավը
բաղկացած է ներքև խորացող փակ խողավականման թունելներից և թունելները իրար կապող
հանգույցներից: Երաշխավորվում է, որ ցանկացած հանգույցից կարելի է գնալ մեկ ուրիշ հանգույց
միայն մեկ ճանապարհով (այլ կերպ ասած քարանձավի հանգույցները և թունելները առաջացնում
են ծառ): Ամեն հանգույցում կա ճիշտ մեկ քար (ինչ որ գույնի): Ալադինը ունի երկու քարանձավների
քարտեզները, և այժմ նա և իր ընկերը պետք է որոշեն, թե ինչպես հավաքել մաքսիմալ
քանակությամբ քարեր՝ խուսափելով դժբախտությունից: Քանի որ քարանձավները կախարդական
էին, քարանձավում թույլատրվում է վերձնել վերևից ներքև ընթացող հաջորդական քարեր (ընդ
որում հերթականությունը կարևոր է): Բացի դրանից ցանկացած պահի, երբ առաջին քարանձավից
քար են հեռացնում նույն գույնի քար պետք է հեռացվի երկրորդ քարանձավից (իհարկե երկրորդ
քարանձավից քար հեռացնելու դեպքում հեռացված քարերը պետք է բավարարեն նախորդ
պայմանին): Այսինքն՝ ընհանուր առմամբ նրանք պետք է գտնեն ամենաերկար (հանգույցների
քանակի իմաստով) ճանապարը վերևից նեքև իջնող և հաջորդական այնպես որ նույն տիպի
(վերևից ներքև իջնող և հաջորդական) ճանապրհ լինի երկրորդ քարանձավում, ընդ որում, եթե
երկու ճանապարհներով էլ միաժամանակ իջնենք, պետք է հանդիպենք նույն գույնի քարեր, նույն

հերթականությամբ: Տե՜ս նկարը, որը համպատասխանում է օրինակին:

Այստեղ օպտիմալ ճանապարհը գծված է կանաչ գույնով: Քանի որ քարանձավները շատ մեծ էին և այդ ժամանակ դեռ չկաին հաշվիչ մեքենաներ Ալադինը այդպես էլ չհասավ իր բաղձանքին: Այժմ ձեր ժամանկն է հասել:

Մուտք„

Մուտքի առաջին տողում տրված է N₁, N₂  համապատասխանաբար առաջին և երկրորդ քարանձավների հանգույցների քանակները: Հաջորդ տողում տրված են N₁ հատ բնական թիվ,
ամեն հանգույցի գույնը (հանգույցները համարակալված են  1-ից սկսված և քարանձավի մուտքը 1-ին հանգույցում է), հաջորդ  N₁-1 տողերից յուրաքանչյուրը  2 իրար միացված հանգույցների
համարներ են: Նույն կերպ տրված է երկրորդ քարանձավը:

Ելք„

Ելքում պետք է արտածել մի թիվ, ամենաերկար այդպիսի ճանապարհի թունելների քանակը:

Օրինակ

Մուտք„.
7 6
1 2 1 3 4 5 6
1 2
1 3
2 4
4 5
5 6
5 7
2 1 3 1 4 7
1 2
1 3
2 4
3 5
6 5

Ելք„.
3