Գտնել ծառի դիամետրը
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով 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