После того, как Виталий был отчислен из университета, он увлекся теорией графов.
Особенно Виталию нравились циклы нечетной длины, в которых каждая вершина встречается не более одного раза.
Виталию стало интересно, как решать следующую задачу. Задан неориентированный граф из n вершин и m ребер, необязательно связный, без кратных ребер и петель. Нужно найти t — минимальное количество ребер, которые нужно добавить в заданный граф таким образом, чтобы образовался простой цикл нечетной длины, состоящий из более чем одной вершины. Кроме того, ему надо найти w — количество способов добавить t ребер так, чтобы образовался цикл нечетной длины (состоящий из более чем одной вершины). Запрещается добавлять петли или кратные рёбра.
Два способа добавить ребра в граф считаются одинаковыми, если в них совпадают множества добавляемых рёбер.
Так как Виталий уже не учится в университете, он обратился к вам за помощью в решении этой задачи.
Выходные данные
Выведите в первую строку выходных данных через пробел два целых числа t и w — минимальное количество ребер, которое необходимо добавить в граф, чтобы образовался простой цикл нечетной длины, состоящий из более чем одной вершины, в котором каждая вершина встречается не более одного раза, и количество способов сделать это.