Монокарп нарисовал неориентированный граф из $$$n$$$ вершин и $$$m$$$ рёбер. Он хочет покрасить каждую вершину в красный или синий цвет так, чтобы у каждой вершины был хотя бы один сосед другого цвета. Ему нужно посчитать количество подходящих раскрасок.
Монокарп — пещерный человек: он знает только числа $$$1$$$, $$$2$$$ и «много» (любое число больше $$$2$$$). Про ноль он не знает, поэтому, если допустимых раскрасок нет, его мозг плавится.
Помогите Монокарпу посчитать допустимые раскраски на его языке. Две раскраски считаются различными, если хотя бы одна вершина имеет в них разные цвета.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$; $$$0 \le m \le \min\left(\frac{n(n-1)}{2}, 3 \cdot 10^5\right)$$$) — количество вершин и рёбер.
Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — номера вершин, соединённых $$$i$$$-м ребром. В графе нет петель и кратных рёбер.
Дополнительные ограничения на входные данные:
Для каждого набора входных данных выведите в отдельной строке:
43 11 23 21 21 33 31 22 31 34 31 22 33 4
Brain Melt2ManyMany
