Problem f Cockroach Escape Networks Bug powder dust an mugwump jism And the wild boys runnin''ound Interzone trippin Justin Warfield. Bomb the bass Bill Lee shares his apartment with a group of cockroaches. The bugs are smart and have several nests inside the apartment. When they are inside one of the nests, Bill can not catch them. Some pairs of nests are connected by cockroach trails, and it takes one unit of time to run from one nest along a trail to any neighbouring nest. However, it takes a lot of the cockroaches resources to make sure that it is possible to run from any nest to any other nest along a sequence of trail t still maintain all of the trails in good condition. What they need is to destroy some of the trails, bi There are n nests in the room, and each nest has at least n-l cockroaches in it at any moment. In case of emergency(when Bill comes into the room and turns on the light), the roaches go into a state of panic- from every nest, n-l roaches strat running, one to every other nest along the trails Several roaches can run along the same trail without interfering with each other. The time it takes for the last cockroach to reach its destination is called the Emergency Response Time. The cockroaches are smart and always choose the shortest path Your task is, given a description of the cockroaches network, find the set, T, of trails that need to be kept so that it is possible to reach any nest B from any nest A along a path in T. If there are multiple such sets, pick the one that has the fewest trails. If there is still a tie, pick the one that guarantees the smallest Emergency Response Time. Print that time Input The first line of input gives the number of cases, Nn test cases follow. Each one starts with a line containing the integers n( the number of nests)and m(the number of trails). The next m lines will give the pairs of nests that are connected by a trail. The nests are numbered from 0 to n-1. n is at most 25. There will be no trails from a node to itself and no duplicate trails Output For each test case, output the line"Case #x: where x is the number of the test case. On the next line, print the smallest possible Emergency Response Time. Print an empty line after each test8 Problem F Cockroach Escape Networks Time Limit: 3 seconds "Bug powder dust an' mugwump jism And the wild boys runnin' 'round Interzone trippin'" Justin Warfield, Bomb the Bass Bill Lee shares his apartment with a group of cockroaches. The bugs are smart and have several nests inside the apartment. When they are inside one of the nests, Bill can not catch them. Some pairs of nests are connected by cockroach trails, and it takes one unit of time to run from one nest along a trail to any neighbouring nest. However, it takes a lot of the cockroaches' resources to maintain all of the trails in good condition. What they need is to destroy some of the trails, but still make sure that it is possible to run from any nest to any other nest along a sequence of trails. There are n nests in the room, and each nest has at least n-1 cockroaches in it at any moment. In case of emergency (when Bill comes into the room and turns on the light), the roaches go into a state of panic - from every nest, n-1 roaches strat running, one to every other nest along the trails. Several roaches can run along the same trail without interfering with each other. The time it takes for the last cockroach to reach its destination is called the Emergency Response Time. The cockroaches are smart and always choose the shortest path. Your task is, given a description of the cockroaches' network, find the set, T, of trails that need to be kept so that it is possible to reach any nest B from any nest A along a path in T. If there are multiple such sets, pick the one that has the fewest trails. If there is still a tie, pick the one that guarantees the smallest Emergency Response Time. Print that time. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing the integers n (the number of nests) and m (the number of trails). The next m lines will give the pairs of nests that are connected by a trail. The nests are numbered from 0 to n-1. n is at most 25. There will be no trails from a node to itself and no duplicate trails. Output For each test case, output the line "Case #x:", where x is the number of the test case. On the next line, print the smallest possible Emergency Response Time. Print an empty line after each test case