CF542E Playing on Graph

Vova and Marina love offering puzzles to each other. Today Marina offered Vova to cope with the following task. Vova has a non-directed graph consisting of $ n $ vertices and $ m $ edges without loops and multiple edges. Let's define the operation of contraction two vertices $ a $ and $ b $ that are not connected by an edge. As a result of this operation vertices $ a $ and $ b $ are deleted and instead of them a new vertex $ x $ is added into the graph, and also edges are drawn from it to all vertices that were connected with $ a $ or with $ b $ (specifically, if the vertex was connected with both $ a $ and $ b $ , then also exactly one edge is added from $ x $ to it). Thus, as a result of contraction again a non-directed graph is formed, it contains no loops nor multiple edges, and it contains $ (n-1) $ vertices. Vova must perform the contraction an arbitrary number of times to transform the given graph into a chain of the maximum length. A chain of length $ k $ ( $ k>=0 $ ) is a connected graph whose vertices can be numbered with integers from $ 1 $ to $ k+1 $ so that the edges of the graph connect all pairs of vertices $ (i,i+1) $ ( $ 1

N/A

N/A

In the first sample test you can contract vertices $ 4 $ and $ 5 $ and obtain a chain of length $ 3 $ . In the second sample test it is initially impossible to contract any pair of vertexes, so it is impossible to achieve the desired result. In the third sample test you can contract vertices $ 1 $ and $ 2 $ and obtain a chain of length $ 2 $ .