Գտնել ծառի դիամետրը
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
v գագաթ ունեցող ծառ, պիտի գտնի այդ ծառի դիամետրը: Դիամետրը երկու ամենահեռու գագաթների միջև գտվող ճանապարհի երկարությունն է:Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
v (1 ≤ v ≤ 100000):Հաջորդ
v-1 տողերում տրված են զույգ整数եր v1, v2 (1 ≤ v1, v2 ≤ v), որոնք նշանակում են, որ գագաթ v1-ը կապված է գագաթ v2-ի հետ (և հակառակը):Ելք
Ծրագիրը ելքում պետք է տպի տվյալ ծառի դիամետրը:
Օրինակներ
Մուտք | Ելք |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
Հուշում 1
Դուք կարող եք մի քանի անգամ իրականացնել DFS (Depth-First Search) տարբեր ելակետերից:
Հուշում 2
Կարող եք սկսել DFS-ը գագաթ 1-ից և գտնել ամենահեռու գագաթը (թեև Սա ծառ է, ուստի ցիկլեր չկան, կարող եք չկիրառել BFS):
Այնուհետև սկսեք DFS-ը recién հայտնաբերված ամենահեռու գագաթից և գտեք նրանից ամենահեռու գագաթը:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB