Двофарбування#6065
Дано граф, визначте, скількома способами його можна розфарбувати, використовуючи не більше двох кольорів. Жодне ребро не повинно з'єднувати вершини одного кольору.
Перший рядок вхідних даних містить число — кількість тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа (1 \leq V \leq 30) та (0 \leq E \leq 1000). Кожен з наступних рядків містить два цілі числа та (0 \leq a \leq V-1, 0 \leq b \leq V-1), що вказують на існування двонаправленого ребра між та . Не буде жодних самопетель або дубльованих ребер. Останній рядок вхідних даних буде порожнім.
Для кожного тестового випадку виведіть кількість способів, якими можна розфарбувати граф, використовуючи лише два кольори. Якщо граф неможливо розфарбувати не більше ніж двома кольорами, виведіть .
Приклад 1