Вова и Марина любят предлагать друг другу головоломки. Сегодня Марина предложила Вове справиться со следующим заданием.

У Вовы есть неориентированный граф из n вершин и m рёбер, в котором нет петель и кратных рёбер. Определим операцию склейки двух не соединённых ребром вершин a и b. В результате этой операции вершины a и b стираются, а вместо них в граф добавляется новая вершина x, и из неё проводятся рёбра во все вершины, которые были соединены с a или с b (в частности, если вершина была соединена и с a, и с b, то также добавляется ровно одно ребро из x в неё). Таким образом, в результате склейки вновь образуется неориентированный граф без петель и кратных рёбер, но содержащий уже (n - 1) вершин.

Вова должен, выполнив склейку произвольное количество раз, преобразовать имеющийся граф в цепочку максимальной длины. Цепочкой длины k (k ≥ 0) называется связный граф, вершины которого можно пронумеровать числами от 1 до k + 1 таким образом, что рёбра графа будут соединять все пары вершин (i, i + 1) (1 ≤ i ≤ k) и только их. В частности, граф, состоящий из одной вершины, представляет собой цепочку длины 0. Вершины, образованные в результате склейки разрешается использовать в дальнейших операциях склейки.

Рисунок иллюстрирует склейку двух вершин, помеченных красным цветом.

Помогите Вове справиться с заданием его подруги. Найдите максимальную длину цепочки, которую можно получить из имеющегося графа, либо определите, что получить цепочку невозможно.