SPOJ in Armenian

Թզուկները շարունակում են փնտրել նախնիների ոսկին Մենավոր սարի խորքերում։ Մենավոր սարի խորքերը իրենցից ներկայացնում են n քարանձավներ, որոնցից մի քանիսը միացված են երկկողմանի անցումներով։ Ընդ որում, յուրաքանչյուր քարանձավից անցումներով կարելի է հասնել ցանկացած այլ քարանձավ, և դա կարելի է անել մի եղանակով։

Թզուկները բաժանվեցին երկու ջոկատի և սկսեցին իրենց որոնումները, համապատասխանաբար, u0 և v0 քարանձավներից: Ջոկատներից յուրաքանչյուրի թզուկները միասին են տեղաշարժվում։ Ջոկատը մի քարանձավը հետազոտում է մեկ րոպեում, որից հետո անցումով արագ տեղափոխվում է հարևան քարանձավներից մեկը։ Ընդ որում թզուկները, այն քարանձավը, որտեղ իրենք, կամ մյուս ջոկատի թզուկները, եղել են, չեն մտնում։ Երկու ջոկատները երբեք միևնույն քարանձավը չեն մտնում։ Եթե ջոկատներից մեկը չի կարողանում տեղաշարժվել այս կանոններով, երկու ջոկատներն էլ անմիջապես դադարեցնում են գանձերի որոնումը։

Մենավոր սարի խորքերը լավագույնս հետազոտելու համար թզուկները ցանկանում են, որ իրենց որոնումները, որքան հնարավոր է, երկար շարունակվեն։ Տրված են Մենավոր սարի քարանձավների քարտեզը և թզուկների նախնական դիրքերը, պարզեք, թե առավելագույնը որքան կարող են տևել գանձերի որոնումները։

Մուտքը

Առաջին տողում տրված է քարանձավների n (2 <= n <= 200 000) քանակը։ Հաջորդ n-1 տողերում տրված են քարանձավների միջև անցումները։ Յուրաքանչյուր տողում գրված են երկու v և u (1 <= v,u <= n) քարանձավների համարներ, որոնք միացված են անցումով։ Հաջորդ տողում տրված են այն քարանձավների v0 և u0 (1 <= v0, u0 <= n, v0 ≠ u0) համարները, որտեղ սկզբում գտնվում են թզուկների երկու ջոկատները։

Ելքը

Արտածեք մի ամբողջ թիվ՝ գանձերը որոնելու առավելագույն ժամանակը։

Օրինակներ

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

Ելքը.
2

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

Ելքը.
4