Sonya and Tree

Sonya is a very smart girl, so Danya wants to give her something interesting. He thought about it for a long time and decided that the best gift would be a tree. This tree has $N$ vertices (numbered $1$ through $N$); of course, it is a connected graph with $N-1$ edges connecting those vertices. Danya realised that an ordinary tree probably would not surprise Sonya. Therefore, he decided to plac