DZY loves chemistry, and he enjoys mixing chemicals.

DZY has n chemicals, and m pairs of them will react. He wants to pour these chemicals into a test tube, and he needs to pour them in one by one, in any order. 

Let's consider the danger of a test tube. Danger of an empty test tube is 1. And every time when DZY pours a chemical, if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by 2. Otherwise the danger remains as it is.

Find the maximum possible danger after pouring all the chemicals one by one in optimal order.


-----Input-----

The first line contains two space-separated integers n and m $(1 \leq n \leq 50 ; 0 \leq m \leq \frac{n(n - 1)}{2})$.

Each of the next m lines contains two space-separated integers x_{i} and y_{i} (1 ≤ x_{i} < y_{i} ≤ n). These integers mean that the chemical x_{i} will react with the chemical y_{i}. Each pair of chemicals will appear at most once in the input.

Consider all the chemicals numbered from 1 to n in some order.


-----Output-----

Print a single integer — the maximum possible danger.


-----Examples-----
Input
1 0

Output
1

Input
2 1
1 2

Output
2

Input
3 2
1 2
2 3

Output
4



-----Note-----

In the first sample, there's only one way to pour, and the danger won't increase.

In the second sample, no matter we pour the 1st chemical first, or pour the 2nd chemical first, the answer is always 2.

In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).

Difficulty: MEDIUM
Tags: Spanning trees

Graph traversal

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def dfs(t):
	nonlocal used, g
	used[t] = True
	for k in g[t]:
		if not used[k]:
			used[k] = True
			dfs(k)
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(lambda e: int(e) - 1, input().split())
	g[x] += [y]
	g[y] += [x]
used = [False] * n
r = n
for i in range(n):
	if not used[i]:
		r -= 1
		dfs(i)
print(2 ** r)


MAX_N = 52
root = [0 for _ in range(MAX_N)]
n = 0
m = 0
res = 1

def findRoot(u):
	if root[u] == u:
		return u
	else:
		root[u] = findRoot(root[u])
		return root[u]

def unionSet(u, v):
	global res
	rootu = findRoot(u)
	rootv = findRoot(v)
	if rootu != rootv:
		res *= 2
		root[rootu] = rootv

def solve():
	(n, m) = map(int, input().strip().split())
	for i in range(1, n + 1):
		root[i] = i
	for i in range(m):
		(u, v) = map(int, input().strip().split())
		unionSet(u, v)
	print(res)
solve()


import sys
input = sys.stdin.readline
from math import log2, log, ceil

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return res

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	while x != link[x]:
		x = link[x]
	return x

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(1000000.0 + 5)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter

def find_parent(parent, i):
	if parent[i] == -1:
		return i
	if parent[i] != -1:
		return find_parent(parent, parent[i])
(n, m) = map(int, input().split())
parent = [-1] * n
cnt = 0
for i in range(m):
	(u, v) = map(int, input().split())
	xroot = find_parent(parent, u - 1)
	yroot = find_parent(parent, v - 1)
	if xroot != yroot:
		cnt += 1
		parent[xroot] = yroot
print(2 ** cnt)


[n, m] = [int(i) for i in input().split()]
adj = [[] for i in range(n + 1)]
for j in range(m):
	[a, b] = [int(i) for i in input().split()]
	adj[a].append(b)
	adj[b].append(a)
visited = [False] * (n + 1)

def dfs(start):
	visited[start] = True
	for x in adj[start]:
		if not visited[x]:
			dfs(x)
components = 0
for i in range(1, n + 1):
	if not visited[i]:
		dfs(i)
		components += 1
print(2 ** (n - components))


import os
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from io import BytesIO, IOBase
from itertools import accumulate, combinations, combinations_with_replacement, groupby, permutations, product
from math import acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians, sin, sqrt, tan
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits

def inp():
	return int(input())

def inlist():
	return list(map(int, input().split()))

def instr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def dfs(u):
	c = 1
	stk = []
	stk.append(u)
	visited[u] = True
	while len(stk) > 0:
		u = stk.pop()
		for v in a[u]:
			if not visited[v]:
				c += 1
				visited[v] = True
				stk.append(v)
	return c
(n, e) = invr()
a = defaultdict(lambda : [])
for i in range(e):
	(x, y) = invr()
	a[x].append(y)
	a[y].append(x)
visited = [False] * (n + 1)
res = 1
for i in range(1, n + 1):
	if not visited[i]:
		p = dfs(i)
		res *= 2 ** (p - 1)
print(res)


from queue import Queue
(n, m) = [int(x) for x in input().split(' ')]
v = []
for _ in range(n + 1):
	v.append([])
for _ in range(m):
	(x, y) = [int(a) for a in input().split(' ')]
	v[x].append(y)
	v[y].append(x)
s = [False] * (n + 1)
r = 1
for i in range(1, n + 1):
	if not s[i]:
		q = Queue()
		q.put(i)
		s[i] = True
		while not q.empty():
			vc = q.get()
			vt = v[vc]
			for vct in vt:
				if not s[vct]:
					r <<= 1
					q.put(vct)
					s[vct] = True
print(r)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 99999999999999999999999999999999

def outIn(x):
	print(x, flush=True)
	return input()

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		danger = 1
		graph = [[] for i in range(n + 1)]
		vis = [False] * (n + 1)
		for i in range(m):
			(a, b) = ria()
			graph[a].append(b)
			graph[b].append(a)

		def dfs(i):
			vis[i] = True
			for j in graph[i]:
				if not vis[j]:
					dfs(j)
		cc = 0
		for i in range(1, n + 1):
			if not vis[i]:
				cc += 1
				dfs(i)
		wi(2 ** (n - cc))
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


from collections import defaultdict
from sys import stdin

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return [str(x) for x in stdin.readline().split()]

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		self.gdict = gdict

	def edges(self):
		return self.find_edges()

	def find_edges(self):
		edges = []
		for node in self.gdict:
			for nxNode in self.gdict[node]:
				if {nxNode, node} not in edges:
					edges.append({node, nxNode})
		return edges

	def get_vertices(self):
		return list(self.gdict.keys())

	def add_vertix(self, node):
		self.gdict[node] = []

	def add_edge(self, node1, node2):
		self.gdict[node1].append(node2)
		self.gdict[node2].append(node1)

	def dfsUtil(self, v):
		self.visit[v] = 1
		for i in self.gdict[v]:
			if self.visit[i] == 0:
				self.dfsUtil(i)
				self.topsort *= 2

	def dfs(self):
		(self.cnt, self.topsort, self.visit) = (0, 1, defaultdict(int))
		for i in self.get_vertices():
			if self.visit[i] == 0:
				self.dfsUtil(i)
				self.cnt += 1
		return self.topsort
(n, m) = arr_inp(1)
che = graph()
for i in range(m):
	(x, y) = arr_inp(1)
	che.add_edge(x, y)
print(che.dfs())


def recursive_dfs(graph, start, path=[]):
	path = path + [start]
	for node in graph[start]:
		if not node in path:
			path = recursive_dfs(graph, node, path)
	return path

def iterative_dfs(graph, start, path=[]):
	q = [start]
	while q:
		v = q.pop(0)
		if v not in path:
			path = path + [v]
			q = graph[v] + q
	return path

def iterative_bfs(graph, start, path=[]):
	q = [start]
	while q:
		v = q.pop(0)
		if not v in path:
			path = path + [v]
			q = q + graph[v]
	return path
(nodes, edges) = list(map(int, input().split(' ')))
graph = {}
for i in range(nodes):
	graph[i] = []
for i in range(edges):
	(a, b) = list(map(int, input().split(' ')))
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
marked = [False] * nodes
num = 0
for i in range(nodes):
	if not marked[i]:
		for j in iterative_dfs(graph, i):
			marked[j] = True
		num += 1
print(2 ** (nodes - num))


(n, m) = map(int, input().split())
r = [[] for i in range(n)]
mk = [0] * n
c = 0

def dfs(x):
	global c
	mk[x] = 1
	c += 1
	for i in range(len(r[x])):
		if mk[r[x][i]] == 0:
			dfs(r[x][i])
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	r[a].append(b)
	r[b].append(a)
jj = 1
for i in range(n):
	if mk[i] == 0:
		dfs(i)
		jj = jj * 2 ** (c - 1)
		c = 0
print(jj)


def main():

	def dfs(v):
		used[v] = 1
		for i in graph[v]:
			if not used[i]:
				dfs(i)
	(n, m) = [int(i) for i in input().split()]
	graph = [[] for i in range(n)]
	for i in range(m):
		(x, y) = [int(i) for i in input().split()]
		graph[x - 1].append(y - 1)
		graph[y - 1].append(x - 1)
	used = [0 for i in range(n)]
	components = 0
	for i in range(n):
		if not used[i]:
			components += 1
			dfs(i)
	print(2 ** (n - components))
main()


import sys
import queue
sys.setrecursionlimit(100000)
INF = int(10000000.0 + 1)
MAX = 100005
parents = []
ranks = []
size = []
n = 0

def init():
	global parents, ranks, size
	parents = [i for i in range(MAX)]
	ranks = [0 for i in range(MAX)]
	size = [1 for i in range(MAX)]

def findSet(u):
	if parents[u] != u:
		parents[u] = findSet(parents[u])
	return parents[u]

def unionSet(u, v):
	up = findSet(u)
	vp = findSet(v)
	if up == vp:
		return
	if ranks[up] < ranks[vp]:
		parents[up] = vp
	elif ranks[vp] < ranks[up]:
		parents[vp] = up
	else:
		ranks[vp] += 1
		parents[up] = vp

def main():
	global n
	(n, m) = map(int, input().split())
	init()
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		unionSet(u, v)
	M = {}
	for i in range(n):
		root = findSet(i)
		if root not in M:
			M[root] = 1
		else:
			M[root] += 1
	ans = 1
	if len(M) > 0:
		for setSize in M.values():
			ans *= max(1, 2 ** (setSize - 1))
	print(ans)
main()


from sys import stdout
from sys import stdin

def get():
	return stdin.readline().strip()

def getf():
	return [int(i) for i in get().split()]

def put(a, end='\n'):
	stdout.write(str(a) + end)

def putf(a, sep=' ', end='\n'):
	stdout.write(sep.join([str(i) for i in a]) + end)

def bfs(g, v, i):
	v[i] = False
	q = [i]
	usd = set()
	while q:
		t = q.pop()
		usd.add(t)
		for j in g[t]:
			v[j] = False
			if j not in usd:
				q.append(j)
	return usd
from collections import defaultdict as dd

def main():
	(n, k) = getf()
	g = dd(list)
	for i in range(k):
		(x, y) = getf()
		g[x - 1] += [y - 1]
		g[y - 1] += [x - 1]
	res = 0
	v = [True] * n
	for u in range(n):
		if v[u] == True:
			bfs(g, v, u)
			res += 1
	put(1 << n - res)
main()


def union(p, n, x, y):
	x = p[x]
	y = p[y]
	for i in range(1, n + 1):
		if p[i] == x:
			p[i] = y

def main():
	(n, m) = [int(i) for i in input().split()]
	if m == 0:
		print(1)
		return
	edges = []
	for i in range(m):
		(x, y) = [int(i) for i in input().split()]
		edges.append([x, y])
	p = [i for i in range(n + 1)]
	for (x, y) in edges:
		union(p, n, x, y)
	k = len(set(p)) - 1
	print(2 ** (n - k))
main()


def dfs(v, root):
	nonlocal cnt
	if used[v]:
		return
	used[v] = True
	for j in range(len(G[v])):
		to = G[v][j]
		dfs(to, root)
	if v == root:
		cnt += 1
cnt = 0
(n, e) = map(int, input().split())
G = [[] for i in range(n)]
for i in range(e):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	G[a].append(b)
	G[b].append(a)
used = [False for i in range(n)]
for v in range(n):
	dfs(v, v)
print(2 ** (n - cnt))


graph = {}
nm = input().split(' ')
(n, m) = (int(nm[0]), int(nm[1]))
for i in range(0, n):
	e = []
	graph[i] = e
for i in range(0, m):
	jk = input().split(' ')
	(j, k) = (int(jk[0]) - 1, int(jk[1]) - 1)
	graph[j].append(k)
	graph[k].append(j)

def get_component():
	for g in graph:
		curr = g
		break
	visited = []
	seen = []
	seen.append(curr)
	while len(seen) != 0:
		visited.append(seen[0])
		for e in graph[seen[0]]:
			if e in visited or e in seen:
				pass
			else:
				seen.append(e)
		del seen[0]
	for i in visited:
		del graph[i]
	return len(visited)
res = 1
while len(graph) != 0:
	cs = get_component()
	res = res * 2 ** (cs - 1)
print(res)


import sys
from collections import deque
mod = 10 ** 9 + 7
fast_reader = sys.stdin.readline
fast_writer = sys.stdout.write

def input():
	return fast_reader().strip()

def print(*argv):
	fast_writer(' '.join((str(i) for i in argv)))
	fast_writer('\n')
for _ in range(1):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		d[i] = []
	for i in range(m):
		(x, y) = map(int, input().split())
		x = x - 1
		y = y - 1
		d[x].append(y)
		d[y].append(x)
	visited = set()
	ans = 1
	for i in range(n):
		if i in visited:
			continue
		c = 0
		q = deque()
		q.append(i)
		while len(q) != 0:
			t = q.popleft()
			if t in visited:
				continue
			else:
				visited.add(t)
				c += 1
				for j in d[t]:
					q.append(j)
		ans *= max(1, 2 ** (c - 1))
	print(ans)


import sys, os.path
from collections import *
from heapq import *
from copy import *
import math
mod = 10 ** 9 + 7
read = lambda : map(int, input().split())
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, m) = map(int, input().split())
g = [list() for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)

def dfs(v):
	vis[v] = 1
	for u in g[v]:
		if not vis[u]:
			dfs(u)
vis = [0] * (n + 1)
clr = 1
ans = n
for i in range(1, n + 1):
	if not vis[i]:
		dfs(i)
		ans -= 1
print(2 ** ans)


from sys import stdin, stdout
from os import path
if path.exists('input.txt'):
	stdin = open('input.txt', 'r')
from collections import defaultdict
danger = 1

def dfs(visited, node, amr):
	visited[node] = 1
	for item in amr[node]:
		if visited[item] == 0:
			global danger
			danger *= 2
			dfs(visited, item, amr)
(x, y) = map(int, stdin.readline().strip().split())
amr = defaultdict(list)
for _ in range(y):
	(a, b) = map(int, stdin.readline().strip().split())
	amr[a].append(b)
	amr[b].append(a)
visited = [0] * (x + 1)
for i in range(1, x + 1):
	if visited[i] == 0:
		dfs(visited, i, amr)
print(danger)


path = 0
res = 1

def dfs(p):
	global res, path, marked, g
	marked[p] = True
	path += 1
	if path > 1:
		res *= 2
	for nv in g[p]:
		if not marked[nv]:
			dfs(nv)
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
	g[y - 1].append(x - 1)
marked = [False for _ in range(n)]
for i in range(n):
	if not marked[i]:
		path = 0
		dfs(i)
print(res)


(n, m) = map(int, input().split())
gr = {i: set() for i in range(n)}
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	gr[a].add(b)
	gr[b].add(a)
used = set()
ans = 1
for v in range(n):
	if v not in used:
		c = 0
		q = [v]
		used.add(v)
		while q:
			u = q.pop()
			for uu in gr[u]:
				if uu not in used:
					q.append(uu)
					used.add(uu)
					c += 1
		ans *= 2 ** c
print(ans)


path = []

def dfs(graph, node):
	global path
	path.append(node)
	for i in graph.get(node):
		if i not in path:
			dfs(graph, i)
(n, m) = map(int, input().split())
a = {}
for i in range(m):
	(x, y) = map(int, input().split())
	if x not in a:
		a.setdefault(x, [y])
	else:
		a[x].append(y)
	if y not in a:
		a.setdefault(y, [x])
	else:
		a[y].append(x)
for i in range(1, n + 1):
	if i not in a:
		a.setdefault(i, [])
dfs(a, 1)
totalpath = []
t = 0
for i in range(2, n + 1):
	if len(path) > 1:
		t += len(path) - 1
	totalpath += path
	path = []
	if i not in totalpath:
		dfs(a, i)
print(2 ** t)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
from collections import defaultdict, deque
import heapq
getcontext().prec = 25
MOD = pow(10, 9) + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def dfs(i):
	visted[i] = True
	for j in g[i]:
		if visted[j] == False:
			dfs(j)
(n, m) = map(int, input().split(' '))
visted = [False] * n
g = {}
for i in range(n):
	g[i] = []
for i in range(m):
	(x, y) = map(int, input().split(' '))
	g[x - 1].append(y - 1)
	g[y - 1].append(x - 1)
c = 0
for i in range(n):
	if visted[i]:
		continue
	c += 1
	dfs(i)
print(1 << n - c)


from collections import defaultdict, deque

def dfs(node):
	v[0] += 1
	if not visited[node]:
		visited[node] = True
		for neibour in g[node]:
			if not visited[neibour]:
				dfs(neibour)
(n, m) = map(int, input().split())
g = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
visited = [False] * (n + 1)
ans = 1
for i in range(1, n + 1):
	v = [0]
	dfs(i)
	if v[0] == 1:
		continue
	ans = ans * pow(2, v[0] - 1)
print(ans)


class Graph(object):

	def __init__(self, num_nodes):
		self.num_nodes = num_nodes
		self.adj_list = {}

	def add_edge(self, a, b):
		if a in self.adj_list:
			if b not in self.adj_list[a]:
				self.adj_list[a].append(b)
		else:
			self.adj_list[a] = []
			self.adj_list[a].append(b)
		if b in self.adj_list:
			if a not in self.adj_list[b]:
				self.adj_list[b].append(a)
		else:
			self.adj_list[b] = []
			self.adj_list[b].append(a)

	def generate_freq_dict(self):
		freq_dict = {}
		for (k, v) in self.adj_list.items():
			freq_dict[k] = len(v)
		return freq_dict

	def generate_sorted_freq_dict(self):
		freq_dict = self.generate_freq_dict()
		sfd = [(k, freq_dict[k]) for k in sorted(freq_dict, key=freq_dict.get, reverse=True)]
		return sfd

	def print_graph(self):
		print(self.adj_list)

	def get_sfd_with_src(self, src):
		freq_dict = self.generate_freq_dict()
		sfd = [(k, freq_dict[k]) for k in sorted(freq_dict, key=freq_dict.get, reverse=True) if k in self.adj_list[src]]
		return sfd

def read_graph():
	(n, m) = map(int, input().split())
	g = Graph(n)
	for _ in range(m):
		(a, b) = map(int, input().split())
		g.add_edge(a, b)
	return g

def rec_dfs(g, top, visited, d):
	visited[top] = True
	src_sfd = g.get_sfd_with_src(top)
	for x in src_sfd:
		next = x[0]
		if not visited[next]:
			d[0] = d[0] * 2
			rec_dfs(g, next, visited, d)

def dfs():
	g = read_graph()
	sfd = g.generate_sorted_freq_dict()
	d = [1]
	visited = {}
	for i in range(1, g.num_nodes + 1):
		visited[i] = False
	while len(sfd) > 0:
		top = sfd.pop()[0]
		if not visited[top]:
			rec_dfs(g, top, visited, d)
	print(d[0])
dfs()


(n, m) = map(int, input().split())
l = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	l[a - 1].append(b - 1)
	l[b - 1].append(a - 1)
r = 1
nexts = set()
while not all([x is None for x in l]):
	if nexts:
		ch = nexts.pop()
		r *= 2
	else:
		i = 0
		while l[i] is None:
			i += 1
		if i == len(l):
			break
		ch = i
	for a in l[ch]:
		nexts.add(a)
		l[a].remove(ch)
	l[ch] = None
print(r)


from collections import defaultdict

def dfs(node, graph, vis):
	global count
	vis[node] = True
	count += 1
	for i in graph[node]:
		if not vis[i]:
			dfs(i, graph, vis)
(n, m) = map(int, input().split())
if m == 0:
	print(1)
else:
	graph = defaultdict(list)
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	vis = [False] * (n + 1)
	ans = 0
	ans = 0
	for i in range(1, n + 1):
		global count
		count = 0
		if not vis[i]:
			dfs(i, graph, vis)
			ans += 1
	print(pow(2, n - ans))


def read_input():
	global n, m, edge
	(n, m) = map(int, input().split())
	edge = []
	for i in range(m):
		(u, v) = map(int, input().split())
		edge.append((u - 1, v - 1))

def init():
	global lab
	lab = [-1] * n

def find_set(u):
	global lab
	if lab[u] < 0:
		return u
	lab[u] = find_set(lab[u])
	return lab[u]

def union(r, s):
	global lab
	lab[r] = s

def solve():
	global edge, cc
	init()
	cc = n
	for e in edge:
		r = find_set(e[0])
		s = find_set(e[1])
		if r != s:
			union(r, s)
			cc -= 1
	print(2 ** (n - cc))
read_input()
solve()


from collections import defaultdict, deque, Counter, OrderedDict

def main():
	(n, m) = map(int, input().split())
	visited = [0] * (n + 1)
	d = [1] * (n + 1)
	adj = [[] for i in range(n + 1)]

	def dfs(i, p):
		if visited[i]:
			return
		visited[i] = 1
		d[p] += 1
		for j in adj[i]:
			dfs(j, p)
	for i in range(m):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	for i in range(1, n + 1):
		if visited[i] == 0:
			d[i] = 0
			dfs(i, i)
	ans = 0
	for i in range(1, n + 1):
		ans += d[i] - 1
	print(2 ** ans)
main()


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
(n, m) = (int(i) for i in input().split())
d = {}
for i in range(n):
	d[i] = []
for j in range(m):
	(x, y) = (int(i) for i in input().split())
	d[x - 1].append(y - 1)
	d[y - 1].append(x - 1)
p = 1
v = [0] * n
for i in range(n):
	if v[i] == 0:
		c = 0
		queue = [i]
		v[i] = 1
		while queue != []:
			s = queue.pop(0)
			c += 1
			for j in d[s]:
				if v[j] == 0:
					v[j] = 1
					queue.append(j)
		p *= pow(2, c - 1)
print(p)


def bfs(i, visited, a):
	visited[i] = True
	a[i].sort()
	t = 0
	for j in a[i]:
		if visited[j[1]] == False:
			t += bfs(j[1], visited, a)
	return t + 1

def main():
	mode = 'filee'
	if mode == 'file':
		f = open('test.txt', 'r')
	get = lambda : [int(x) for x in (f.readline() if mode == 'file' else input()).split()]
	[n, m] = get()
	a = {}
	for i in range(1, n + 1):
		a[i] = []
	visited = [False] * (n + 1)
	for z in range(m):
		[x, y] = get()
		a[x].append(y)
		a[y].append(x)
	length = [0] * (n + 1)
	length[0] = [0, 0]
	for i in range(1, n + 1):
		length[i] = [len(a[i]), i]
	for i in range(1, n + 1):
		for j in range(len(a[i])):
			a[i][j] = [length[a[i][j]][0], a[i][j]]
	length.sort()
	ans = 0
	for i in length[1:]:
		if visited[i[1]] == False:
			ans += bfs(i[1], visited, a) - 1
	print(2 ** ans)
	if mode == 'file':
		f.close()
main()


def main():
	(n, m) = map(int, input().split())
	(l, r) = ([[a] for a in range(n + 1)], 0)
	for _ in range(m):
		(a, b) = map(int, input().split())
		(la, lb) = (l[a], l[b])
		if la is not lb:
			if len(la) < len(lb):
				(la, lb) = (lb, la)
			la += lb
			for b in lb:
				l[b] = la
	for la in l:
		a = len(la)
		if a > 1:
			r += a - 1
			la.clear()
	print(1 << r)
main()


def dfs(a, vis, mr):
	mr[0] += 1
	vis[a] = 1
	for g in range(0, len(r[a])):
		if vis[r[a][g]] == 1:
			continue
		dfs(r[a][g], vis, mr)
x = input('').split(' ')
nodes = int(x[0])
paths = int(x[1])
r = []
for g in range(3000):
	r.append([])
vis = [0] * 3000
for g in range(paths):
	m = input('').split(' ')
	rrr = int(m[0])
	rr = int(m[1])
	r[rrr].append(rr)
	r[rr].append(rrr)
ans = 1
for g in range(1, nodes + 1):
	mr = [0]
	if vis[g] == 1:
		continue
	l = dfs(g, vis, mr)
	ans *= pow(2, mr[0] - 1)
print(ans)


a = list(map(int, input().split()))
n = a[0]
m = a[1]
graph = list(([] for i in range(n)))
visited = list((False for i in range(n)))
arr = []

def dfs(v):
	visited[v] = True
	for i in graph[v]:
		if not visited[i]:
			dfs(i)
for i in range(m):
	b = list(map(int, input().split()))
	arr.append([b[0] - 1, b[1] - 1])
	graph[b[0] - 1].append(b[1] - 1)
	graph[b[1] - 1].append(b[0] - 1)
v = 0
for i in range(n):
	if not visited[i]:
		dfs(i)
		v += 1
ans = 2 ** (n - v)
print(ans)


(n, m) = map(int, input().split())
p = list(range(n + 1))
h = [0] * (n + 1)

def pred(x):
	if x != p[x]:
		p[x] = pred(p[x])
	return p[x]

def union(a, b):
	(a, b) = (pred(a), pred(b))
	if h[a] < h[b]:
		(a, b) = (b, a)
	p[b] = a
	if h[a] == h[b]:
		h[a] += 1
for _ in range(m):
	(i, j) = map(int, input().split())
	union(i, j)
for i in range(n + 1):
	pred(i)
print(2 ** (n - len(set(p)) + 1))


from collections import defaultdict, deque

def main():
	(n, m) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(m):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	nodes2visit = set(range(1, n + 1))
	ans = 0
	while nodes2visit:
		start_node = next(iter(nodes2visit))
		cnt = 0
		queue = deque([start_node])
		while queue:
			node = queue.pop()
			cnt += 1
			nodes2visit.discard(node)
			for nxt in graph[node]:
				if nxt in nodes2visit:
					queue.appendleft(nxt)
					nodes2visit.discard(nxt)
		ans += cnt - 1
	print(2 ** ans)
main()


from collections import defaultdict, deque
(n, m) = map(int, input().strip().split())
graph = defaultdict(lambda : set())
visited = set()
for i in range(m):
	(x, y) = map(int, input().strip().split())
	graph[x].add(y)
	graph[y].add(x)

def dfs(start):
	count = 1
	stack = deque([start])
	visited.add(start)
	while stack:
		node = stack.pop()
		for neb in graph[node]:
			if neb not in visited:
				visited.add(neb)
				count += 1
				stack.append(neb)
	return count
res = 1
for i in range(1, n + 1):
	if i not in visited:
		nodes = dfs(i)
		res *= 2 ** (nodes - 1)
print(res)


(n, m) = map(int, input().split())
p = list(range(n + 1))
s = [{i} for i in p]
for i in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (p[x], p[y])
	if x != y:
		if len(s[x]) < len(s[y]):
			for k in s[x]:
				p[k] = y
				s[y].add(k)
			s[x].clear()
		else:
			for k in s[y]:
				p[k] = x
				s[x].add(k)
			s[y].clear()
q = 0
for p in s:
	if p:
		q += len(p) - 1
print(1 << q)


__author__ = 'artyom'
read = lambda : map(int, input().split())
(n, m) = read()
graph = [set() for _ in range(n + 1)]
for __ in range(m):
	(x, y) = read()
	graph[x].add(y)
	graph[y].add(x)
visited = set()

def dfs(start, counter):
	stack = [start]
	while stack:
		vertex = stack.pop()
		if vertex not in visited:
			counter *= 2
			visited.add(vertex)
			stack.extend(graph[vertex] - visited)
	return counter // 2
res = 1
for v in range(1, n + 1):
	if v not in visited:
		res = dfs(v, res)
print(res)


idx = []
size = []

def root(x):
	while x != idx[x]:
		idx[x] = idx[idx[x]]
		x = idx[x]
	return x

def connected(p, q):
	return root(p) == root(q)

def union(p, q):
	i = root(p)
	j = root(q)
	if size[i] < size[j]:
		idx[i] = j
		size[j] += size[i]
	else:
		idx[j] = i
		size[i] += size[j]
sa = input().split(' ')
chems = int(sa[0])
reacts = int(sa[1])
for t in range(chems):
	idx.append(t)
size = [1] * chems
for reaction in range(reacts):
	sa = input().split(' ')
	union(int(sa[0]) - 1, int(sa[1]) - 1)
for t in range(len(idx)):
	idx[t] = root(idx[t])
print(2 ** (chems - len(set(idx))))


def dfs(v):
	used[v] = 1
	for i in graph[v]:
		if not used[i]:
			dfs(i)
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1] += [b - 1]
	graph[b - 1] += [a - 1]
used = [0 for i in range(n)]
counter = 0
for i in range(n):
	if not used[i]:
		dfs(i)
		counter += 1
print(2 ** (n - counter))


from collections import defaultdict

def dfs(g, vis, node):
	global cnt
	cnt += 1
	vis[node] = True
	for i in g[node]:
		if vis[i] == False:
			dfs(g, vis, i)
	return
(n, m) = map(int, input().strip().split())
g = defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().strip().split())
	g[x].append(y)
	g[y].append(x)
ans = 1
vis = [False] * (n + 1)
for i in range(1, n + 1):
	if vis[i] == False:
		cnt = 0
		dfs(g, vis, i)
		ans *= 2 ** (cnt - 1)
print(ans)


from sys import stdin, stdout
from collections import defaultdict
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))

def dfs(src):
	global ans, sz
	vis[src] = 1
	sz += 1
	for neigh in g[src]:
		if not vis[neigh]:
			dfs(neigh)
for _ in range(1):
	(n, eg) = lst()
	g = defaultdict(list)
	for i in range(eg):
		(u, v) = lst()
		g[u] += [v]
		g[v] += [u]
	ans = 0
	vis = [0] * (1 + n)
	for i in range(n):
		if not vis[i]:
			sz = 0
			dfs(i)
			ans += sz - 1
	print(1 << ans)


from collections import defaultdict

class Graph(object):

	def __init__(self, connections, directed=False):
		self.visited = {}
		self._graph = defaultdict(set)
		self._digraph = directed
		self.add_connections(connections)

	def add_connections(self, connections):
		for (node1, node2) in connections:
			self.add(node1, node2)

	def add(self, node1, node2):
		self._graph[node1].add(node2)
		if not self._digraph:
			self._graph[node2].add(node1)

	def DFS(self, starting_node, cnt):
		if starting_node not in self.visited:
			self.visited[starting_node] = 1
			cnt += 1
			for neighbour in self._graph[starting_node]:
				cnt = max(cnt, self.DFS(neighbour, cnt))
		return cnt

	def connected_component(self):
		ans = 0
		for i in self._graph:
			if i not in self.visited:
				ans += self.DFS(i, 0) - 1
		return 2 ** ans
(v, e) = map(int, input().split())
if e == 0:
	print(1)
else:
	connections = []
	for i in range(e):
		(f, t) = map(int, input().split())
		connections.append((f, t))
	g = Graph(connections)
	ans = g.connected_component()
	print(ans)


import sys, math, bisect
from random import randint
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def isPrime(n, k=5):
	if n < 2:
		return True
	for i in range(0, k):
		a = randint(1, n - 1)
		if pow(a, n - 1, n) != 1:
			return False
	return True
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
import string
(n, m) = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
	i = list(map(int, input().split()))
	graph[i[0]].append(i[1])
	graph[i[1]].append(i[0])
cc = []
visited = set()

def dfs(v, visited, cc):
	visited.add(v)
	cc.append(v)
	for node in graph[v]:
		if node not in visited:
			dfs(node, visited, cc)
for i in range(1, n + 1):
	stack = []
	if i not in visited:
		dfs(i, visited, stack)
		cc.append(stack)
ans = 1
for i in cc:
	ans *= 2 ** (len(i) - 1)
print(ans)


from sys import stdin
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())

def find(z):
	while z != v[z]:
		v[z] = v[v[z]]
		z = v[z]
	return z
(n, m) = R()
ans = 1
v = [i for i in range(n)]
p = [0] * n
for i in range(m):
	(x, y) = R()
	v[find(y - 1)] = find(x - 1)
for i in range(n):
	p[find(i)] += 1
for i in p:
	if i:
		ans *= 2 ** (i - 1)
print(ans)


(n, m) = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u].append(v)
	graph[v].append(u)
visited = [False] * n
cnt = 0

def dfs(v):
	visited[v] = True
	global cnt
	cnt += 1
	for u in graph[v]:
		if not visited[u]:
			dfs(u)
ans = 1
for i in range(n):
	if not visited[i]:
		cnt = 0
		dfs(i)
		ans *= 2 ** (cnt - 1)
print(ans)


def solve(graph):
	grps = []
	n = len(graph)
	vis = [False for i in range(n)]
	for i in range(n):
		if not vis[i]:
			ct = 0
			vis[i] = True
			wait = [i]
			while wait:
				currNode = wait.pop()
				ct += 1
				for node in graph[currNode]:
					if not vis[node]:
						vis[node] = True
						wait.append(node)
			grps.append(ct)
	return sorted(grps)
(n, m) = map(int, input().split())
graph = dict(zip(range(n), [[] for i in range(n)]))
for i in range(m):
	(src, dest) = map(int, input().split())
	graph[src - 1].append(dest - 1)
	graph[dest - 1].append(src - 1)
groups = solve(graph)
ans = 1
for i in groups:
	ans <<= i - 1
print(ans)


import sys
sys.setrecursionlimit(100000000)
(mod, MOD) = (1000000007, 998244353)
from collections import deque, Counter, OrderedDict, defaultdict

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def expo(a, b):
	result = 1
	while b > 0:
		if b & 1:
			result *= a
		a *= a
		b >>= 1
	return result

def dfs(curr):
	visited[curr] = True
	stack = [curr]
	component = [curr]
	while stack:
		x = stack.pop()
		for child in mydict[x]:
			if not visited[child]:
				visited[child] = True
				stack.append(child)
				component.append(child)
	return component
(n, m) = get_ints()
mydict = defaultdict(list)
for i in range(m):
	(a, b) = get_ints()
	mydict[a].append(b)
	mydict[b].append(a)
visited = [False] * (n + 1)
components = []
for i in range(1, n + 1):
	if not visited[i]:
		components.append(dfs(i))
ans = 1
for i in components:
	if len(i) > 1:
		ans *= expo(2, len(i) - 1)
print(ans)


import sys

def input():
	return sys.stdin.readline().strip()
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
if m > 0:
	for i in range(m):
		(x, y) = map(int, input().split())
		edge[x - 1].append(y - 1)
		edge[y - 1].append(x - 1)
	count = 0
	visited = [0 for i in range(n)]
	next = []
	pos = 0
	while pos < n:
		if len(next) == 0:
			while pos < n and visited[pos]:
				pos += 1
			if pos < n:
				visited[pos] = 1
				for i in edge[pos]:
					next.append(i)
			else:
				break
		elif not visited[next[0]]:
			visited[next[0]] = 1
			for i in edge[next[0]]:
				next.append(i)
			count += 1
			del next[0]
		else:
			del next[0]
	print(2 ** count)
else:
	print(1)


from collections import defaultdict
g = defaultdict(list)

def dfs(i, visited):
	visited.add(i)
	for j in g[i]:
		if j not in visited:
			dfs(j, visited)
(n, e) = map(int, input().split())
for _ in range(e):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)
visited = set()
count = 0
for i in g:
	if i not in visited:
		dfs(i, visited)
		count += 1
print(pow(2, len(visited) - count))


import math

def Find(a, group):
	ag = group[a]
	if ag != a:
		ag = Find(ag, group)
	group[a] = ag
	return ag

def Union(a, b, group):
	ag = Find(a, group)
	bg = Find(b, group)
	if ag != bg:
		group[ag] = bg

def solve():
	(n, m) = [int(i) for i in input().split()]
	group = [i for i in range(n)]
	for _ in range(m):
		(x, y) = [int(i) - 1 for i in input().split()]
		Union(x, y, group)
	count = {}
	for i in range(n):
		ig = Find(i, group)
		if ig in count:
			count[ig] = count[ig] + 1
		else:
			count[ig] = 0
	power = sum(count.values())
	print(int(math.pow(2, power)))
solve()


from collections import deque, defaultdict
cnt = 0

def dfs(node):
	global cnt
	visited[node] = True
	cnt += 1
	for i in g[node]:
		if not visited[i]:
			dfs(i)
(n, m) = map(int, input().split())
if m == 0:
	print(1)
	exit(0)
g = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
visited = [False] * (n + 1)
res = 1
for i in range(1, n + 1):
	cnt = 0
	dfs(i)
	cnt -= 1
	if cnt > 0:
		res *= pow(2, cnt)
print(res)


(n, m) = map(int, input().split())
arr = [x for x in range(0, n + 1)]
d = 1
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (arr[a], arr[b])
	while a != arr[a]:
		a = arr[a]
	while b != arr[b]:
		b = arr[b]
	if a != b:
		arr[b] = a
		d *= 2
print(d)


(n, m) = map(int, input().split())
e = [[] for x in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	e[x].append(y)
	e[y].append(x)
c = set(range(1, n + 1))
val = 2 ** n
while c:
	s = c.pop()
	dfs = [s]
	val //= 2
	while dfs:
		cur = dfs.pop()
		for nxt in e[cur]:
			if nxt in c:
				dfs.append(nxt)
				c.remove(nxt)
print(val)


MAX = 1770
listEdge = []
root = [u for u in range(MAX)]

def findRoot(u):
	if root[u] == u:
		return u
	else:
		root[u] = findRoot(root[u])
		return root[u]

def unionSet(u, v):
	rootu = findRoot(u)
	rootv = findRoot(v)
	if rootu != rootv:
		root[rootu] = rootv

def solve():
	danger = 1
	(n, m) = map(int, input().strip().split())
	for _ in range(m):
		(u, v) = map(int, input().strip().split())
		listEdge.append([u, v])
	root = [u for u in range(n + 1)]
	for edge in listEdge:
		if findRoot(edge[0]) != findRoot(edge[1]):
			danger *= 2
			unionSet(edge[0], edge[1])
	print(danger)
solve()


def find(fa, x):
	if fa[x] == x:
		return x
	else:
		fa[x] = find(fa, fa[x])
		return fa[x]
(n, m) = map(int, input().split())
fa = []
for i in range(n):
	fa.append(i)
ans = 1
for i in range(m):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	if find(fa, x) != find(fa, y):
		ans *= 2
		fa[find(fa, x)] = fa[y]
print(ans)


from collections import defaultdict, deque, Counter, OrderedDict

def find(a, par):
	if a == par[a]:
		return a
	par[a] = find(par[a], par)
	return par[a]

def merge(a, b, siz, par):
	a = find(a, par)
	b = find(b, par)
	if a == b:
		return
	if siz[a] < siz[b]:
		(a, b) = (b, a)
	par[b] = a
	siz[a] += siz[b]

def main():
	(n, m) = map(int, input().split())
	par = list(range(n + 1))
	siz = [1] * (n + 1)
	for i in range(m):
		(a, b) = map(int, input().split())
		merge(a, b, siz, par)
	ans = 0
	for i in range(1 + n):
		if i == find(i, par):
			ans += siz[i] - 1
	print(2 ** ans)
main()


(n, m) = map(int, input().split())
k = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	k[a].append(b)
	k[b].append(a)
l = 1
vis = [True] * (n + 1)
for i in range(1, n + 1):
	if vis[i]:
		q = [i]
		vis[i] = False
		while len(q) != 0:
			x = q.pop()
			for j in k[x]:
				if vis[j]:
					l *= 2
					q.append(j)
					vis[j] = False
print(l)


class CodeforcesTask445BSolution:

	def __init__(self):
		self.result = ''
		self.n_m = []
		self.reactions = []

	def read_input(self):
		self.n_m = [int(x) for x in input().split(' ')]
		for x in range(self.n_m[1]):
			self.reactions.append([int(y) for y in input().split(' ')])

	def process_task(self):
		reactions_cnt = 0
		danger = 1
		reaction_groups = {}
		graph = [[[], -1] for x in range(self.n_m[0])]
		for react in self.reactions:
			graph[react[0] - 1][0].append(react[1])
			graph[react[1] - 1][0].append(react[0])
		starts = [x + 1 for x in range(self.n_m[0])]
		while starts:
			starting = starts.pop(-1)
			if graph[starting - 1][1] == -1:
				reactions_cnt += 1
				reaction_groups[reactions_cnt] = 1
				graph[starting - 1][1] = reactions_cnt
				to_visit = graph[starting - 1][0]
				while to_visit:
					visiting = to_visit.pop(-1)
					if graph[visiting - 1][1] == -1:
						graph[visiting - 1][1] = reactions_cnt
						reaction_groups[reactions_cnt] += 1
						to_visit += graph[visiting - 1][0]
		for (key, val) in reaction_groups.items():
			danger *= 2 ** (val - 1)
		self.result = str(danger)

	def get_result(self):
		return self.result
Solution = CodeforcesTask445BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


def getroot(lab, u):
	if lab[u] == -1:
		return u
	lab[u] = getroot(lab, lab[u])
	return lab[u]

def union(lab, cou, a, b):
	if cou[a] > cou[b]:
		cou[a] += cou[b]
		lab[b] = a
	else:
		cou[b] += cou[a]
		lab[a] = b

def inp():
	return map(int, input().split())

def solve():
	(n, m) = inp()
	lab = [-1 for i in range(n)]
	cou = [0 for i in range(n)]
	danger = 1
	for i in range(m):
		(u, v) = inp()
		u = getroot(lab, u - 1)
		v = getroot(lab, v - 1)
		if u != v:
			danger *= 2
			union(lab, cou, u, v)
	print(danger)
solve()


def solution():
	(n, m) = [int(x) for x in input().split(' ')]
	if m == 0:
		return 1
	graph = {}
	for i in range(m):
		(x, y) = input().split(' ')
		if x not in graph:
			graph[x] = []
		if y not in graph:
			graph[y] = []
		graph[x].append(y)
		graph[y].append(x)
	ans = 0
	already = []
	for current in graph:
		nodes = nbrConnectedNodes(current, graph, already)
		if len(nodes) > 0:
			already += nodes
			ans += len(nodes) - 1
	return 2 ** ans

def nbrConnectedNodes(s, graph, blackList):
	if s not in graph or s in blackList:
		return []
	queu = [s]
	ans = 0
	nodes = []
	while len(queu):
		current = queu[0]
		del queu[0]
		for i in graph[current]:
			if i not in nodes:
				if i not in queu:
					queu.append(i)
				nodes.append(i)
	return nodes
print(solution())


import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root, vis):
		queue = [root]
		queue = deque(queue)
		ans = 0
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			ans += 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1
		return ans

	def dfs(self, root, ans):
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i != self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0] * self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i] == 0:
				q.append(i)
		while len(q) != 0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		if vis != self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue
(n, m) = map(int, input().split())
g = Graph(n, False)
for i in range(m):
	(x, y) = map(int, input().split())
	g.addEdge(x - 1, y - 1)
vis = [0] * n
ans = 1
for i in range(n):
	if not vis[i]:
		c = g.bfs(i, vis)
		ans = ans * 2 ** (c - 1)
print(ans)


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [0] * n
		self.size = n

	def find(self, id):
		if id != self.parent[id]:
			self.parent[id] = self.find(self.parent[id])
		return self.parent[id]

	def union(self, id1, id2):
		(par1, par2) = (self.find(id1), self.find(id2))
		if par1 == par2:
			return
		if self.rank[par1] > self.rank[par2]:
			self.parent[par2] = par1
		else:
			self.parent[par1] = par2
			if self.rank[par1] == self.rank[par2]:
				self.rank[par2] += 1
		self.size -= 1

	def normalize(self):
		for id in range(len(self.parent)):
			self.find(id)
(n, m) = map(int, input().split())
dsu = UnionFind(n)
for _ in range(m):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	dsu.union(a, b)
print(1 << n - dsu.size)


from collections import defaultdict
d = defaultdict(list)
(n, m) = map(int, input().split())
pr = 1

def DFS(visited, d, x):
	stack = [x]
	c = 0
	while len(stack):
		temp = stack.pop()
		visited[temp] = 1
		c = c + 1
		for j in d[temp]:
			if visited[j] == 0:
				stack.append(j)
				visited[j] = 1
	return c
t = 0
for j in range(m):
	(x, y) = map(int, input().split())
	d[x].append(y)
	d[y].append(x)
visited = [0 for i in range(n + 1)]
for j in range(1, n + 1):
	if visited[j] == 0:
		t = t + DFS(visited, d, j) - 1
print(max(pow(2, t), 1))


MAX = 55
parent = []

def makeSet():
	global parent
	parent = [i for i in range(MAX + 1)]

def findSet(u):
	while u != parent[u]:
		u = parent[u]
	return u

def unionSet(u, v):
	up = findSet(u)
	vp = findSet(v)
	parent[up] = vp
(n, m) = map(int, input().split())
makeSet()
for i in range(m):
	(a, b) = map(int, input().split())
	unionSet(a, b)
p = [0] * MAX
res = 1
for i in range(1, n + 1):
	if p[findSet(i)] != 0:
		res *= 2
	p[findSet(i)] += 1
print(res)


def depth_first_search(x):
	stack = [x]
	visited[x] = 1
	sz = 1
	while stack:
		a = stack.pop()
		for i in tree[a]:
			if not visited[i]:
				visited[i] = 1
				stack.append(i)
				sz += 1
	return sz
(n, m) = map(int, input().split())
tree = {i: [] for i in range(1, n + 1)}
visited = [0] * (n + 1)
for i in range(m):
	(xi, yi) = map(int, input().split())
	tree[xi].append(yi)
	tree[yi].append(xi)
lis = []
count = 1
for i in range(1, n + 1):
	if not visited[i]:
		visited[i] = 1
		c = depth_first_search(i)
		lis.append(c)
danger = 1
lis.sort()
for i in lis:
	if i != 1:
		danger *= 2 ** (i - 1)
print(danger)


import sys

def addEdge(n0, n1, graph):
	if n0 in graph:
		graph[n0] = graph[n0] + [n1]
	else:
		graph[n0] = [n1]

def flatten(listOfLists):
	newlist = []
	for l in listOfLists:
		newlist = newlist + l
	return newlist

def zusKomp2(graph):
	nodes = list(graph.keys())
	zusKompn = {}
	for node in nodes:
		if node in flatten(zusKompn.values()):
			continue
		pointer = 0
		zusKompn[node] = [node]
		while pointer < len(zusKompn[node]):
			posNewNodes = graph[zusKompn[node][pointer]]
			for n in posNewNodes:
				if n not in zusKompn[node]:
					zusKompn[node].append(n)
			pointer = pointer + 1
	return zusKompn
x = sys.stdin.read()
ls = x.splitlines()
(ns, ms) = ls[0].split()
(n, m) = (int(ns), int(ms))
graph = {}
for l in ls[1:]:
	nodes = l.split()
	(n0, n1) = (int(nodes[0]), int(nodes[1]))
	addEdge(n0, n1, graph)
	addEdge(n1, n0, graph)
isolatednodes = set(range(1, n + 1)) - set(graph.keys())
for i in isolatednodes:
	graph[i] = []
zusKompn = zusKomp2(graph)
print(2 ** sum(list(map(lambda x: len(x) - 1, zusKompn.values()))))


(n, m) = map(int, input().split())
parent = [i for i in range(n + 1)]

def get_parent(x):
	if parent[x] != x:
		parent[x] = get_parent(parent[x])
	return parent[x]
for _ in range(m):
	(x, y) = map(int, input().split())
	parent[get_parent(x)] = get_parent(y)
ans = 1 << n
for i in range(1, n + 1):
	if get_parent(i) == i:
		ans /= 2
print(int(ans))


def dfs(cur, visited, graph):
	visited.add(cur)
	for adj in graph[cur]:
		if adj not in visited:
			dfs(adj, visited, graph)
from collections import defaultdict
(n, m) = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
	(x, y) = map(int, input().split())
	graph[x].append(y)
	graph[y].append(x)
components = 0
visited = set()
for i in range(1, n + 1):
	if i not in visited:
		dfs(i, visited, graph)
		components += 1
print(2 ** (n - components))


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, m) = I()
p = [i for i in range(n)]
an = 0

def find(x):
	while x != p[x]:
		x = p[x]
	return x

def union(a, b):
	global an
	x = find(a)
	y = find(b)
	if x != y:
		p[y] = x
		an += 1
for i in range(m):
	(a, b) = I()
	union(a - 1, b - 1)
print(2 ** an)


(n, m) = map(int, input().split())
g = [[False] * n for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g[x][y] = g[y][x] = True
u = [False] * n
d = 1

def dfs(p):
	global d
	for j in range(n):
		if g[p][j] and (not u[j]):
			u[j] = True
			d *= 2
			dfs(j)
for i in range(n):
	if not u[i]:
		u[i] = True
		dfs(i)
print(d)


from sys import setrecursionlimit
setrecursionlimit(10000)
(n, m) = list(map(int, input().split()))
a = [[False for j in range(n + 1)] for i in range(n + 1)]
b = [False for i in range(n + 1)]
for i in range(m):
	(x, y) = list(map(int, input().split()))
	a[x][y] = True
	a[y][x] = True

def r(i):
	if b[i]:
		return 0
	b[i] = True
	s = 0
	for j in range(1, n + 1):
		if a[i][j]:
			s += r(j)
	return s + 1
o = 1
for i in range(1, n + 1):
	if not b[i]:
		o *= 2 ** (r(i) - 1)
print(o)


def gf(x):
	if fa[x] != x:
		fa[x] = gf(fa[x])
	return fa[x]
(n, m) = map(int, input().split())
fa = list(range(n + 1))
for _ in range(m):
	(x, y) = map(int, input().split())
	fa[gf(x)] = gf(y)
ans = 2 ** n
for i in range(1, n + 1):
	if gf(i) == i:
		ans //= 2
print(ans)


used = set()

def dfs(v, root):
	nonlocal cnt
	if v in used:
		return
	used.add(v)
	for to in G[v]:
		dfs(to, root)
	if v == root:
		cnt += 1
cnt = 0
(n, m) = list(map(int, input().split()))
G = [[] for i in range(n)]
for i in range(m):
	(x, y) = list(map(int, input().split()))
	G[x - 1].append(y - 1)
	G[y - 1].append(x - 1)
for v in range(n):
	dfs(v, v)
print(2 ** (n - cnt))


ans = 0

def uniqe(zero, lst):
	global ans
	for i in zero:
		for j in lst[i - 1]:
			if j not in zero:
				ans += 1
				zero.append(j)
z = list(map(int, input().split()))
lst = [[] for i in range(z[0])]
a = []
s = 0
lst_two = []
for i in range(z[1]):
	(x1, x2) = map(int, input().split())
	lst[x2 - 1].append(x1)
	lst[x1 - 1].append(x2)
	a.append(x1)
	a.append(x2)
a = list(set(a))
while len(lst_two) != len(a):
	zero = []
	if a[s] not in lst_two:
		zero.append(a[s])
		uniqe(zero, lst)
		lst_two.extend(zero)
	s += 1
print(2 ** ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
	(components, visited) = ([], [False] * n)

	def dfs(start):
		(component, stack) = ([], [start])
		while stack:
			start = stack[-1]
			if visited[start]:
				stack.pop()
				continue
			else:
				visited[start] = True
				component.append(start)
			for i in graph[start]:
				if not visited[i]:
					stack.append(i)
		return component
	for i in range(n):
		if not visited[i]:
			components.append(dfs(i))
	return components
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	graph = [[] for __ in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x] += [y]
		graph[y] += [x]
	cp = connected_components(n + 1, graph)
	x = len(cp) - 1
	print(2 ** (n - x))


def dfs(pos):
	global usd, adj
	if usd[pos]:
		return 0
	usd[pos] = True
	ans = 1
	for sig in adj[pos]:
		ans += dfs(sig)
	return ans

def main():
	global usd, adj
	pot = 0
	(a, b) = [int(x) for x in input().split()]
	usd = [False for i in range(a)]
	adj = [[] for i in range(a)]
	for i in range(b):
		(x, y) = [int(x) - 1 for x in input().split()]
		adj[x].append(y)
		adj[y].append(x)
	for i in range(a):
		pot += max(0, dfs(i) - 1)
	print(2 ** pot)
main()


def dfs(i):
	used[i] = True
	for j in graph[i]:
		if not used[j]:
			dfs(j)
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a] += [b]
	graph[b] += [a]
used = [False for i in range(n)]
cc = 0
for i in range(n):
	if not used[i]:
		cc += 1
		dfs(i)
print(1 << n - cc)


def dfs(node, visited, f):
	f[0] += 1
	visited[node] = 1
	for j in range(len(graph[node])):
		if visited[graph[node][j]] == 1:
			continue
		else:
			dfs(graph[node][j], visited, f)
(n, m) = map(int, input().split())
visited = [0] * (n + 1)
graph = []
for i in range(n + 1):
	graph.append([])
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
ans = 1
for i in range(1, n + 1):
	f = [0]
	res = dfs(i, visited, f)
	ans *= pow(2, f[0] - 1)
print(ans)


def findp(v):
	if parent[v] == v:
		return v
	r = findp(parent[v])
	parent[v] = r
	return r
(n, m) = map(int, input().split())
parent = [0] * n
for i in range(n):
	parent[i] = i
ans = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (findp(a - 1), findp(b - 1))
	if a != b:
		parent[b] = a
		ans += 1
print(1 << ans)


from collections import defaultdict as ddict, deque

def find_links_count(n, nodes, links):
	queue = deque([n])
	seen = set()
	while queue:
		next = queue.pop()
		if next in seen:
			continue
		seen.add(next)
		nodes.remove(next)
		cdren = links[next]
		cdren = [c for c in cdren if c not in seen]
		queue.extend(cdren)
	return len(seen)
(N, M) = [int(_) for _ in input().split()]
links = ddict(list)
for _ in range(M):
	(A, B) = [int(_) for _ in input().split()]
	links[A].append(B)
	links[B].append(A)
nodes = set([n + 1 for n in range(N)])
danger = 1
while nodes:
	next = nodes.pop()
	nodes.add(next)
	z = find_links_count(next, nodes, links) - 1
	danger *= 2 ** z
print(danger)


def abhi(node, y):
	visited[node] = 1
	comp[y].append(node)
	for j in adj[node]:
		if visited[j] == 0:
			abhi(j, y)
(n, m) = map(int, input().split())
adj = [[] for j in range(n + 1)]
for j in range(m):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
visited = [0] * (n + 1)
comp = [[] for j in range(n + 1)]
u = 1
for j in range(1, n + 1):
	if visited[j] == 0:
		abhi(j, u)
		u += 1
ans = 1
for j in comp:
	if len(j) >= 2:
		ans *= 2 ** (len(j) - 1)
print(ans)


(n, m) = map(int, input().split())
from collections import defaultdict
d = defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().split())
	x = x - 1
	y = y - 1
	d[x].append(y)
	d[y].append(x)
ans = 1
maxi = 0
c = 0
vis = [0] * n
for i in range(n):
	if not vis[i]:
		q = [i]
		c = c + 1
		vis[i] = 1
		while q:
			t = q.pop(0)
			for i in d[t]:
				if not vis[i]:
					vis[i] = 1
					q.append(i)
		maxi = max(maxi, c)
maxi = maxi - 1
print(2 ** (n - c))


def find(x):
	i = prt[x]
	while i != prt[i]:
		i = prt[i]
	return i
(n, m) = map(int, input().split())
prt = [i for i in range(n + 1)]
res = 0
for i in range(m):
	(x, y) = map(int, input().split())
	x1 = find(y)
	y1 = find(x)
	if x1 != y1:
		prt[x1] = y1
		res += 1
print(1 << res)


import sys
import math
import collections
import bisect

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
for t in range(1):
	(n, k) = get_ints()
	if k == 0:
		print(1)
		continue
	connected = []
	for i in range(n):
		connected.append([])
	for i in range(k):
		(x, y) = get_ints()
		connected[x - 1].append(y - 1)
		connected[y - 1].append(x - 1)
	max_connect = 0
	visted = [False] * n
	count = 0
	for i in range(n):
		if visted[i] == True:
			continue
		start = i
		queue = [start]
		count += 1
		while len(queue) > 0:
			pos = queue.pop(0)
			if visted[pos] == True:
				continue
			else:
				visted[pos] = True
			for j in range(len(connected[pos])):
				queue.append(connected[pos][j])
		max_connect = max(count, max_connect)
	print(2 ** (n - max_connect))


class DisjointSet:

	def __init__(self, n):
		self.num_sets = n
		self.parents = list(range(n))
		self.ranks = [0] * n
		self.sizes = [1] * n

	def find(self, j):
		while self.parents[j] != j:
			j = self.parents[j]
		return j

	def union(self, i, j):
		i = self.find(i)
		j = self.find(j)
		if i == j:
			return False
		rd = self.ranks[i] - self.ranks[j]
		if rd == 0:
			self.ranks[i] += 1
		elif rd < 0:
			(i, j) = (j, i)
		self.parents[j] = i
		self.sizes[i] += self.sizes[j]
		self.sizes[j] = 0
		self.num_sets -= 1
		return True

def main():
	(n, m) = list(map(int, input().split()))
	cl = [list(map(int, input().split())) for _ in range(m)]
	ds = DisjointSet(n)
	for (a, b) in cl:
		ds.union(a - 1, b - 1)
	print(2 ** sum([max(0, s - 1) for s in ds.sizes]))
main()


read = lambda : map(int, input().split())
(n, m) = read()
g = [list() for i in range(n + 1)]
for i in range(m):
	(x, y) = read()
	g[x].append(y)
	g[y].append(x)

def dfs(v):
	was[v] = clr
	for u in g[v]:
		if not was[u]:
			dfs(u)
was = [0] * (n + 1)
clr = 1
ans = n
for i in range(1, n + 1):
	if not was[i]:
		dfs(i)
		ans -= 1
		clr += 1
print(2 ** ans)


import math
import bisect
import sys
from collections import OrderedDict
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.DFSUtil(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = []
		cc = 1
		for i in range(self.V):
			visited.append(False)
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				a = len(self.DFSUtil(temp, v, visited))
				cc *= 2 ** (a - 1)
		return cc
(N, M) = invr()
g = Graph(N)
for m in range(M):
	(a, b) = invr()
	g.addEdge(a - 1, b - 1)
print(g.connectedComponents())


def dfs(x):
	l.append(x)
	vis[x] = True
	for i in adj[x]:
		if not vis[i]:
			dfs(i)
(n, m) = map(int, input().split())
from collections import *
adj = defaultdict(list)
vis = defaultdict(lambda : False)
for _ in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
	adj[y].append(x)
l5 = []
for i in range(1, n + 1):
	if not vis[i]:
		l = []
		dfs(i)
		if len(l) > 1:
			l5.append(len(l) - 1)
print(2 ** sum(l5))


import collections as cc
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, m) = I()
ar = []
g = [set() for i in range(n + 1)]
parent = [i for i in range(n + 1)]

def find(x):
	while x != parent[x]:
		x = parent[x]
	return x

def union(x, y):
	a = find(x)
	b = find(y)
	if a != b:
		ar.append(1)
		parent[a] = b
for i in range(m):
	(x, y) = I()
	union(x, y)
print(2 ** sum(ar))


(n, m) = map(int, input().split())
(graph, visited) = ([[] for _ in range(n + 1)], set())
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)

def dfs(element):
	visited.add(element)
	for each in graph[element]:
		if each not in visited:
			dfs(each)
connected = 1
dfs(1)
for i in range(1, n + 1):
	if i not in visited:
		dfs(i)
		connected += 1
print(2 ** (len(visited) - connected))


from collections import defaultdict
(n, m) = list(map(int, input().split()))
graph = defaultdict(list)
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
visited = [False for i in range(n)]
ans = 0
for i in range(n):
	if visited[i] == False:
		visited[i] = True
		q = [i]
		t = 0
		while q != []:
			u = q[0]
			q.pop(0)
			t += 1
			for j in graph[u]:
				if visited[j] == False:
					visited[j] = True
					q.append(j)
		ans += 1
print(pow(2, n - ans))


def main():

	def dfs(index):
		visited[index] = True
		comp.append(index)
		for nb in adj[index]:
			if not visited[nb]:
				dfs(nb)
	(n, m) = map(int, input().split())
	ans = 1
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	visited = [False] * n
	for i in range(n):
		if not visited[i]:
			comp = []
			dfs(i)
			size = len(comp)
			ans = ans * (1 << size - 1)
	print(ans)
main()


from sys import stdin, stdout
from os import path
if path.exists('input.txt'):
	stdin = open('input.txt', 'r')
from collections import defaultdict
danger = 1

def dfs(visited, node, amr):
	visited[node] = 1
	for item in amr[node]:
		if visited[item] == 0:
			global danger
			danger *= 2
			dfs(visited, item, amr)
(x, y) = map(int, stdin.readline().strip().split())
amr = defaultdict(list)
for _ in range(y):
	(a, b) = map(int, stdin.readline().strip().split())
	amr[a].append(b)
	amr[b].append(a)
out = []
visited = [0] * (x + 1)
nodes = [i for i in range(1, x + 1)]
for (key, val) in amr.items():
	out.append((-1 * len(val), key))
out.sort()
for i in range(len(out)):
	size = abs(out[i][0])
	key = out[i][1]
	dfs(visited, key, amr)
print(danger)


import sys
f = sys.stdin
(n, m) = map(int, f.readline().strip().split())
d = [{} for u in range(n)]
for i in range(m):
	(xi, yi) = map(int, f.readline().strip().split())
	d[yi - 1][xi - 1] = 1
	d[xi - 1][yi - 1] = 1

def ff(i, s):
	for k in d[i]:
		if rt[k] == 0:
			rt[k] = s
			ff(k, s)
s = 0
rt = [0 for u in range(n)]
for i in range(n):
	if rt[i] == 0:
		s += 1
		rt[i] = s
		ff(i, s)
print(2 ** (n - s))


def find(x):
	if p[x] == x:
		return x
	else:
		p[x] = find(p[x])
		return p[x]

def union(a, b):
	a = find(a)
	b = find(b)
	if rank[a] < rank[b]:
		p[a] = b
	else:
		p[b] = a
	if rank[a] == rank[b]:
		rank[a] += 1
(n, m) = map(int, input().split())
rank = [0 for i in range(n)]
p = []
for i in range(n):
	p.append(i)
ans = 1
for i in range(m):
	(a, b) = map(int, input().split())
	if find(a - 1) != find(b - 1):
		union(a - 1, b - 1)
		ans *= 2
print(ans)


(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
v = [-1] * n
o = [1]

def dfs(x):
	v[x] = 1
	o[0] *= 2
	for j in g[x]:
		if v[j] == -1:
			dfs(j)
for i in range(n):
	if v[i] == -1:
		dfs(i)
		o[0] = max(1, o[0] // 2)
print(o[0])


counter = 1
lst = []
mx = 100
(n, m) = map(int, input().split())
graph = [[] for i in range(mx)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)

def dfs(n):
	lst.append(n)
	for i in graph[n]:
		if i not in lst:
			dfs(i)
dfs(1)
for x in range(1, n + 1):
	if x not in lst:
		dfs(x)
		counter += 1
print(2 ** (len(lst) - counter))


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List
(n, m) = map(int, input().split())
tree = list(range(n + 1))

def find(st):
	if tree[st] != st:
		tree[st] = find(tree[st])
	return tree[st]
for _ in range(m):
	(u, v) = map(int, input().split())
	tree[find(u)] = find(tree[v])
cnt = collections.defaultdict(int)
for i in range(1, n + 1):
	cnt[find(i)] += 1
ans = 1 << sum((v - 1 for v in cnt.values()))
print(ans)


def main():
	from collections import deque

	def find(k):
		if dsu[k] == k:
			return k
		dsu[k] = find(dsu[k])
		return dsu[k]
	(n, m) = [int(i) for i in input().split()]
	react = [[] for _ in range(n)]
	dsu = list(range(n))
	v = [0] * n
	for _ in range(m):
		(a, b) = [int(i) - 1 for i in input().split()]
		react[a].append(b)
		react[b].append(a)
		a = find(a)
		b = find(b)
		if a != b:
			dsu[a] = b
	size = [0] * n
	for i in range(n):
		dsu[i] = find(i)
		size[dsu[i]] += 1
	sets = list(range(n))
	sets.sort(key=size.__getitem__, reverse=True)
	while sets and size[sets[-1]] == 0:
		del sets[-1]
	ans = 1
	for i in sets:
		ans *= 2 ** (size[i] - 1)
	print(ans)
main()


import sys
from collections import defaultdict
from functools import lru_cache
from collections import Counter

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def visit(graph, node, visited):
	if node in visited:
		return 0
	visited.add(node)
	return 1 + sum((visit(graph, c, visited) for c in graph[node]))

def main(n, edges):
	graph = defaultdict(list)
	for (e1, e2) in edges:
		graph[e1].append(e2)
		graph[e2].append(e1)
	prod = 1
	visited = set()
	for n in graph:
		size = visit(graph, n, visited)
		if size > 0:
			prod *= 2 ** (size - 1)
	print(prod)
arr = []
for (e, line) in enumerate(sys.stdin.readlines()):
	if e == 0:
		(n, _) = mi(line)
	else:
		arr.append(lmi(line))
main(n, arr)


from math import pow

class Node:

	def __init__(self, parent, rank):
		self.parent = parent
		self.rank = rank

	def print(self):
		print(self.parent)
		print(self.rank)

def findRoot(s, u):
	if s[u].parent != u:
		s[u].parent = findRoot(s, s[u].parent)
	return s[u].parent

def union(s, u, v):
	ru = findRoot(s, u)
	rv = findRoot(s, v)
	if ru != rv:
		if s[ru].rank < s[rv].rank:
			s[ru].parent = rv
		elif s[ru].rank > s[rv].rank:
			s[rv].parent = ru
		else:
			s[rv].parent = ru
			s[ru].rank += 1
(n, m) = map(int, input().split())
s = []
for i in range(n + 1):
	s.append(Node(i, 0))
for i in range(m):
	(u, v) = map(int, input().split())
	union(s, u, v)
c = set()
for i in range(1, n + 1):
	c.add(findRoot(s, i))
print(int(pow(2, n - len(c))))


(n, m) = list(map(int, input().split()))
was = [False] * n
arr = []
for i in range(n):
	arr.append([])
for i in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	arr[a].append(b)
	arr[b].append(a)
t = 1
for i in range(n):
	if not was[i]:
		q = [i]
		while q:
			preQ = []
			for g in range(len(q)):
				was[q[g]] = True
				for j in range(len(arr[q[g]])):
					if not was[arr[q[g]][j]]:
						was[arr[q[g]][j]] = True
						preQ.append(arr[q[g]][j])
			t = t << len(preQ)
			q = preQ
print(t)


import itertools
(a, b) = list(map(int, input().split()))
dang = 1
r = [(x, set()) for x in range(a)]
for i in range(b):
	(x, y) = list(map(int, input().split()))
	(x, y) = (x - 1, y - 1)
	r[x][1].add(y)
	r[y][1].add(x)
r = sorted(r, key=lambda x: len(x[1]), reverse=True)
willreact = r[0][1]
del r[0]
while len(r) > 0:
	dr = 0
	for i in range(len(r)):
		if r[i][0] in willreact:
			willreact |= r[i][1]
			dang *= 2
			del r[i]
			dr = 1
			break
	if dr == 0:
		willreact |= r[0][1]
		del r[0]
print(dang)


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

def solve(i, d, visited):
	if i in visited:
		return 1
	ans = 1
	visited.add(i)
	for item in d[i]:
		if item not in visited:
			ans *= 2
			ans = ans * solve(item, d, visited)
	return ans

def main():
	(n, m) = map(int, input().split())
	if m == 0:
		print(1)
		exit()
	d = dict()
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a not in d:
			d[a] = []
		if b not in d:
			d[b] = []
		d[a].append(b)
		d[b].append(a)
	visited = set()
	ans = 1
	for i in range(1, n + 1):
		if i in visited:
			continue
		if i not in d:
			continue
		ans *= solve(i, d, visited)
	print(ans)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


def find(x):
	i = parent[x]
	while i != parent[i]:
		i = parent[i]
	return i
(n, m) = map(int, input().split())
parent = [i for i in range(n + 1)]
ans = 0
for i in range(m):
	(x, y) = map(int, input().split())
	x1 = find(y)
	y1 = find(x)
	if x1 != y1:
		parent[x1] = y1
		ans += 1
print(2 ** ans)


(n, m) = map(int, input().split())
p = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	p[u - 1].append(v - 1)
	p[v - 1].append(u - 1)
visited = [1] * n

def dfs(a):
	cnt = 1
	for x in p[a]:
		if visited[x]:
			visited[x] = 0
			cnt += dfs(x)
	return cnt
seq = []
for i in range(n):
	if visited[i]:
		visited[i] = 0
		seq.append(dfs(i))
ans = 1
for x in seq:
	ans *= 2 ** (x - 1)
print(ans)


cnt = []

def dfs(graph, v):
	used.append(v)
	for neighbour in graph[v]:
		if neighbour not in used:
			cnt.append(1)
			dfs(graph, neighbour)
(n, m) = map(int, input().split())
if m == 0:
	print(1)
	exit(0)
graph = {}
for _ in range(m):
	(a, b) = map(int, input().split())
	if a not in graph.keys():
		graph[a] = []
	if b not in graph.keys():
		graph[b] = []
	graph[a].append(b)
	graph[b].append(a)
used = []
ans = 1
for v in range(1, n + 1):
	if v in graph.keys():
		if v not in used:
			cnt = []
			dfs(graph, v)
			ans *= 2 ** len(cnt)
print(ans)


def dfs(i):
	global g, vis
	vis[i] = 1
	for v in g[i]:
		if not vis[v]:
			dfs(v)
(n, m) = map(int, input().split())
vis = [0] * n
g = [list() for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
cnt = 0
for i in range(n):
	if not vis[i]:
		cnt += 1
		dfs(i)
print(1 << n - cnt)


(n, m) = map(int, input().split())
p = [i for i in range(n + 1)]
r = [0 for i in range(n + 1)]
k = 0

def get(x):
	while p[x] != x:
		x = p[x]
	return x

def union(x, y):
	x = get(x)
	y = get(y)
	if x == y:
		return 0
	if r[x] > r[y]:
		(x, y) = (y, x)
	p[x] = y
	if r[x] == r[y]:
		r[y] += 1
	return 1
for i in range(m):
	(x, y) = map(int, input().split())
	k += union(x, y)
print(2 ** k)


def dfs(t):
	global used, g
	used[t] = True
	for k in g[t]:
		if not used[k]:
			used[k] = True
			dfs(k)
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
	g[y - 1].append(x - 1)
used = [False] * n
ans = n
for i in range(n):
	if not used[i]:
		ans -= 1
		dfs(i)
print(2 ** ans)


def bfs(graph, x, used):
	global danger
	for i in range(len(graph[x])):
		if used[graph[x][i]] != 1:
			used[graph[x][i]] = 1
			danger *= 2
			bfs(graph, graph[x][i], used)
amount = list(map(int, input().split(' ')[:2]))
danger = 1
used = [0] * amount[0]
graph = [list() for i in range(amount[0])]
for i in range(amount[1]):
	tmp = list(map(int, input().split(' ')[:2]))
	graph[tmp[0] - 1].append(tmp[1] - 1)
	graph[tmp[1] - 1].append(tmp[0] - 1)
for i in range(amount[0]):
	if used[i] != 1:
		used[i] = 1
		bfs(graph, i, used)
print(danger)


def findSet(u):
	if u != parent[u]:
		parent[u] = findSet(parent[u])
	return parent[u]

def union(u, v):
	up = findSet(u)
	vp = findSet(v)
	parent[vp] = up
str = input().split(' ')
(n, m) = str
n = int(n)
m = int(m)
parent = list(range(0, n + 1))
dic = {}
c = 0
for i in range(m):
	str = input().split(' ')
	(u, v) = str
	u = int(u)
	v = int(v)
	union(u, v)
for i in range(1, n + 1):
	u = findSet(i)
	if u in dic:
		c += 1
	else:
		dic[u] = 0
print(2 ** c)


(n, m) = map(int, input().split())
p = [i for i in range(n)]
sz = [1 for i in range(n)]

def find(i):
	if i != p[i]:
		p[i] = find(p[i])
	return p[i]

def union(i, j):
	i = find(i)
	j = find(j)
	if i == j:
		return
	if sz[i] > sz[j]:
		sz[i] += sz[j]
		p[j] = i
	else:
		sz[j] += sz[i]
		p[i] = j
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	union(a, b)
ans = 0
ss = set()
for i in range(n):
	ss.add(find(i))
for i in ss:
	ans += sz[i] - 1
print(pow(2, ans))