Մրջյունների թագավոր

Մրջյունների թագավորը ցանկանում է գրավել անտառի ամենամեծ ծառը։ Այն իրենից ներկայացնում է գագաթ և կող ունեցող կապակցված գրաֆ։

Մրջյունները արդեն հասցրել են գրավել և գագաթները։

Մրջյունները տարածվում են հատուկ գործողությունների միջոցով։ Մեկ հատուկ գործողության ընթացքում արդեն գրավված գագաթից մրջյուններ են գնում -ին անմիջական հարևան գագաթ (որը դեռևս գրավված չէ) և գրավում այն։Հատուկ գործողությունը տևում է ընդամենը մեկ րոպե։

Յուրաքանչյուր պահի ցանկացած գրավված գագաթ կարող է մասնակցել ամենաշատը մեկ հատուկ գործողության։ Սակայն տարբեր գրավված գագաթներից կարող է տեղի ունենալ հատուկ գործողություն միարժամանակ։

Թագավորի առողջությունը լավ չէ, այդ պատծառով նա ցանկանում է գտնել մինիմալ ժամանակը (րոպեներով), որը կպահանջվի ամբողջ ծառը գրավելու համար։

Մուտքային տվյալներ

Առաջին տողում տրված են , և բնական թվերը ․ գագաթների քանակը և այն երկու գագաթների համարները, որոնք իսկզբանե գրավված են։

Հաջորդ տողերից յուրաքանչյուրում տրված են երկու տարբեր բնական թվեր` և ․ այն գագաթների համարները, որոնք գրաֆում միացված են կողով։

Տրված գրաֆը ծառ է։

Ելքային տվյալներ

Արտածել մեկ ամբողջ թիվ․ պահանջվող նվազագույն ժամանակը։

Օրինակներ

6 2 1
1 2
2 3
2 4
1 5
5 6

2

10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10

4

Գնահատում