Statement

The city of Pordenone is planning an expansion of its road network. There are N towns (indexed from 0 to N-1) in Pordenone's hinterland and M bidirectional roads (numbered from 0 to M-1) connecting some pairs of towns. For each i = 0,1, …, N-1, road i connects towns U_i and V_i. An expansion plan is any set of roads that contains the currently present roads. E. Domora, the mayor of Pordenone, cannot choose an expansion plan among all the possible ones and is in desperate need of your analytical skills. A cluster C is a non-empty set of towns such that, for each t ∈ C and any other town u, there exists a set of roads connecting (possibly indirectly) t and u if and only if u ∈ C. Note that, given a road network, there is an unique way to partition the towns into clusters. The Scoazza Score of a road network is 2^k, where k is the number of clusters in which the network partitions the towns...