Roads

Sarah is an engineer assigned to build roads between the N towns of Evoland. Towns are assigned IDs from 1 to N. A road connects exactly one pair of towns, and is bidirectional. The mayor of Evoland allocated a very small budget for this project. Thus, Sarah is forced to build as few roads as possible while still keeping all N towns connected via roads. Note that this is an absolute requirement;