Travelling in a tree

Leha likes traveling a lot. In particular he likes discovering new routes in his world which he calls a tree-world. Leha's world is a connected tree of N vertices, so there is a unique path between any pair of vertices a and b. Every day Leha chooses some new pair of vertices and walks along this route. Sometimes he notices that he has already been in some vertices during his previous walks. So n