Единственное различие между простой и сложной версией — ограничение на \(n\).
Дан полный неориентированный граф из \(n\) вершин. Полный граф — это такой граф, где между каждой парой вершин существует ровно одно ребро. Вы должны покрасить ребра этого графа в два цвета, синий и красный (каждое ребро должно быть покрашено в один из этих цветов).
Назовем множество вершин \(S\) связным по красному цвету, если для каждой пары вершин \((v_1, v_2)\), такой, что \(v_1 \in S\) и \(v_2 \in S\), существует путь из \(v_1\) в \(v_2\), проходящий только по вершинам из \(S\) и по красным ребрам. Аналогично, назовем множество вершин \(S\) связным по синему цвету, если для каждой пары вершин \((v_1, v_2)\), такой, что \(v_1 \in S\) и \(v_2 \in S\), существует путь из \(v_1\) в \(v_2\), проходящий только по вершинам из \(S\) и по синим ребрам.
Нужно раскрасить граф так, чтобы выполнялись следующие условия:
- хотя бы одно ребро красное;
- хотя бы одно ребро синее;
- для каждого множества вершин \(S\), такого, что \(|S| \ge 2\), \(S\) связно по красному цвету или по синему цвету, но не по обоим цветам.
Посчитайте количество способов покрасить граф и выведите его по модулю \(998244353\).