SP8324 MILPATR - Military patrol

Dystopia consists of N cities. There are one-way roads connecting some pairs of cities. The dysfunctional state has recently seen a lot of protests to overthrow the tyrannical ruler and the government plans to use military patrol vehicles to make sure that the protests are suppressed. Every patrol vehicle is assigned a sequence of cities. If a patrol vehicle is assigned the cities c $ _{1} $ ,c $ _{2} $ ,...c $ _{k} $ then it starts from the city c $ _{1} $ and takes the direct one-way road to c $ _{2} $ , from there it takes the one-way road to c $ _{3} $ and so on. Finally the vehicle takes the one way road from c $ _{k} $ to c $ _{1} $ . This routine is repeated everyday to keep the protestors perpetually under fear. Now note that: - Every city has to appear in exactly one vehicle's patrol sequence exactly once - Every patrol vehicle has to move - so it has to be assigned more than one city The government does not have any limit on the number of patrol vehicles it can use. However, they want to make sure that the least possible amount of money is spent on the patrol mission and hence they want to minimise the total distance travelled by the patrol vehicles. Given the road network of Dystopia, find the minimum total distance the patrol vehicles need to move so that all the cities can be patrolled. If it is impossible to organise a nationwide patrol with the given constraints, report the same.

First line of the contains T, the number of test cases (T

For each test case output one line. If the patrol can be done, output the minimum total distance that the patrol vehicles have to travel. Otherwise output Impossible