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: interview

Starter code:

Solutions:
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))

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(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)

import itertools

a, b = list(map(int, input().split()))

dang = 1

#w = [x+1 for x in range(a)]
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]

#print('r:', r)
#print('wr:', willreact)

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 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]:
        #print('loc ', i, d, k, s)
        if rt[k]==0:
            rt[k] = s
            ff(k,s)
           # print('loc1 ', i, d, 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('gl ', rt, d, i, s)
 
print(2 ** (n-s))       

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)

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))


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)

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):
  nonlocal 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)

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))


#!/usr/env python3
path = []
def dfs(graph, node):
    nonlocal path
    path.append(node)
    for i in graph.get(node):
        if i not in path:
            dfs(graph, i)

n, m = list(map(int, input().split()))
a = {}
for i in range(m):
    x, y = list(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):
#    print(i - 1, path, sorted(totalpath))
    if len(path) > 1:
        t += len(path) - 1
    totalpath += path
    path = []
    if i not in totalpath:
        dfs(a, i)

print(2 ** t)


def dfs(i):
    used[i] = True;
    for j in graph[i]:
        if not used[j]:
            dfs(j)

n, m = list(map(int, input().split()))
graph = [[] for i in range(n)]
for i in range(m):
    a, b = list(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 find(fa, x) : 
    if fa[x] == x :
        return x
    else :
        fa[x] = find(fa, fa[x])
        return fa[x]
n, m = list(map(int, input().split()))
fa = []
for i in range(n) :
    fa.append(i)
ans = 1
for i in range(m) :
    x, y = [int(x) - 1 for x in input().split()]
    if find(fa, x) != find(fa, y) :
        ans *= 2
        fa[find(fa, x)] = fa[y]
print(ans)



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))

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 = list(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 = list(map(int, input().split()))
    if find(a-1) != find(b-1):
        union(a-1, b-1)
        ans *= 2
print(ans)


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

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(list(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] = []

#print("graph:",graph)
#print("isoliert:",isolatednodes)
zusKompn = zusKomp2(graph)
#print("Zusammenhangskomponenten:",zusKompn)

print(2**(sum(list([len(x)-1 for x in list(zusKompn.values())]))))





idx=[]
size=[]
def root(x):
    while x!=idx[x]:
        #path compression start
        idx[x]=idx[idx[x]]
        #path compression end
        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))))


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)

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)


def recursive_dfs(graph, start, path=[]):
  '''recursive depth first search from start'''
  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=[]):
  '''iterative depth first search from start'''
  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=[]):
  '''iterative breadth first search from start'''
  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))
##graph = {'A':['B','C'],'B':['D','E'],'C':['D','E'],'D':['E'],'E':['A']}
##graph = {0: [1, 4, 5, 9], 1: [0, 2, 4, 6, 8], 2: [1, 3, 5, 7, 8], 3: [2, 7, 9], 4: [0, 1, 9], 5: [0, 2, 9], 6: [1, 9], 7: [2, 3, 9], 8: [1, 2], 9: [0, 3, 4, 5, 6, 7]}
##graph = {'A':['B'], 'B':['A', 'C'], 'C':['B', 'D'], 'D':['C', 'E'], 'E':['D'], 'F':['G'], 'G':['F']}
##print('recursive dfs ', recursive_dfs(graph, 'A'))
##print('iterative dfs ', iterative_dfs(graph, 'A'))
##print('iterative bfs ', iterative_bfs(graph, 'A'))


def recursive_dfs(graph, start, path=[]):
  '''recursive depth first search from start'''
  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=[]):
  '''iterative depth first search from start'''
  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=[]):
  '''iterative breadth first search from start'''
  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 recursive_dfs(graph, i):
      marked[j] = True
    num += 1

print(2**(nodes-num))
##graph = {'A':['B','C'],'B':['D','E'],'C':['D','E'],'D':['E'],'E':['A']}
##graph = {0: [1, 4, 5, 9], 1: [0, 2, 4, 6, 8], 2: [1, 3, 5, 7, 8], 3: [2, 7, 9], 4: [0, 1, 9], 5: [0, 2, 9], 6: [1, 9], 7: [2, 3, 9], 8: [1, 2], 9: [0, 3, 4, 5, 6, 7]}
##graph = {'A':['B'], 'B':['A', 'C'], 'C':['B', 'D'], 'D':['C', 'E'], 'E':['D'], 'F':['G'], 'G':['F']}
##print('recursive dfs ', recursive_dfs(graph, 'A'))
##print('iterative dfs ', iterative_dfs(graph, 'A'))
##print('iterative bfs ', iterative_bfs(graph, 'A'))


def recursive_dfs(graph, start, path=[]):
  '''recursive depth first search from start'''
  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=[]):
  '''iterative depth first search from start'''
  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=[]):
  '''iterative breadth first search from start'''
  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_bfs(graph, i):
      marked[j] = True
    num += 1

print(2**(nodes-num))
##graph = {'A':['B','C'],'B':['D','E'],'C':['D','E'],'D':['E'],'E':['A']}
##graph = {0: [1, 4, 5, 9], 1: [0, 2, 4, 6, 8], 2: [1, 3, 5, 7, 8], 3: [2, 7, 9], 4: [0, 1, 9], 5: [0, 2, 9], 6: [1, 9], 7: [2, 3, 9], 8: [1, 2], 9: [0, 3, 4, 5, 6, 7]}
##graph = {'A':['B'], 'B':['A', 'C'], 'C':['B', 'D'], 'D':['C', 'E'], 'E':['D'], 'F':['G'], 'G':['F']}
##print('recursive dfs ', recursive_dfs(graph, 'A'))
##print('iterative dfs ', iterative_dfs(graph, 'A'))
##print('iterative bfs ', iterative_bfs(graph, 'A'))


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)

def iterative_dfs(graph, start, path=[]):
    visited = {}
    for i in graph:
        visited[i] = []
    q=[start]
    while q:
        v=q.pop(0)
        if not visited[v]:
            visited[v] = True
            path=path+[v]
            q=graph[v]+q
    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))


# 445B

__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)