Building Roads

Byteland has n cities, and m roads between them. The goal is to construct new roads so that there is a route between any two cities. Your task is to find out the minimum number of roads required, and also determine which roads should be built. Input The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,\dots,n. After that, there are m lines