Задача №113822. Ещё одно ребро
Простой неориентированный граф — неориентированный граф без петель и кратных рёбер.
Планарный граф — простой неориентированный граф такой, что его можно разместить на плоскости, то есть, его можно нарисовать на плоскости таким образом, чтобы его рёбра пересекались только по общим вершинам.
Независимое множество — это набор вершин в графе, никакие две из которых не соединены ребром.
Трёхдольный граф — это простой неориентированный граф, чьи вершины можно разделить на три независимых непересекающихся множества.
Вам дан планарный граф. Вам необходимо добавить ровно одно ребро в этот граф. Вы знаете, что невозможно добавить ребро в этот граф, чтобы полученный граф остался планарным. Сколькими способами можно добавить ровно одно ребро в этот граф, чтобы он оказался трёхдольным?
Обратите внимание, что вам запрещено добавлять кратные рёбра или петли, так как полученный граф обязан быть простым. Рёбра a - b и b - a считаются одинаковыми, их нужно считать только один раз.
В первой строке даны два целых числа n и m ( 3 ≤ n , m ≤ 3·10 5 ) — число вершин и рёбер в графе соответственно.
В каждой из следующих m строк даны по два числа a и b ( 1 ≤ a , b ≤ n , a ≠ b ), задающие ребро между вершинами a и b .
Гарантируется, что граф удовлетворяет условиям выше.
Выведите одно число — количество способов добавить одно ребро, чтобы получившийся граф получился трёхдольным.
Программа, верно работающая при n ≤ 10 , будет оцениваться в 15 баллов.
Программа, верно работающая при n ≤ 100 , будет оцениваться в 30 баллов.
Программа, верно работающая при n ≤ 1 000 , будет оцениваться в 60 баллов.
3 3 1 2 1 3 2 3
0
4 6 1 2 3 1 4 1 2 3 3 4 2 4
0
8 18 1 2 1 3 1 4 1 5 1 6 1 7 2 3 3 4 4 5 5 6 6 7 2 7 8 2 8 3 8 4 8 5 8 6 8 7
3