B"There are n cities in Berland. Some pairs of cities are connected by roads. All roads are bidirectional. Each road connects two different cities. There is at most one road between a pair of cities. The cities are numbered from 1 to n . It is known that, from the capital (the city with the number 1 ), you can reach any other city by moving along the roads. The President of Berland plans to improve the country's road network. The budget is enough to repair exactly n-1 roads. The President plans to choose a set of n-1 roads such that: In other words, the set of n-1 roads should preserve the connectivity of the country, and the sum of distances from city 1 to all cities should be minimized (where you can only use the n-1 chosen roads). The president instructed the ministry to prepare k possible options to choose n-1 roads so that both conditions above are met. Write a program that will find k possible ways to choose roads for repair. If there are fewer than k ways, then the program should output all possible valid ways to choose roads. The first line of the input contains integers n , m and k ( 2 <= n <= 2 cdot10^5, n-1 <= m <= 2 cdot10^5, 1 <= k <= 2 cdot10^5 ), where n is the number of cities in the country, m is the number of roads and k is the number of options to choose a set of roads for repair. It is guaranteed that m cdot k <= 10^6 . The following m lines describe the roads, one road per line. Each line contains two integers a_i , b_i ( 1 <= a_i, b_i <= n , a_i ne b_i ) -- the numbers of the cities that the i -th road connects. There is at most one road between a pair of cities. The given set of roads is such that you can reach any city from the capital. Print t ( 1 <= t <= k ) -- the number of ways to choose a set of roads for repair. Recall that you need to find k differe"...