One particularly well-known fact about zombies is that they move and think terribly slowly. While we still don't know why their movements are so sluggish, the problem of laggy thinking has been recently resolved. It turns out that the reason is not (as previously suspected) any kind of brain defect – it's the opposite! Independent researchers confirmed that the nervous system of a zombie is highly complicated – it consists of n brains (much like a cow has several stomachs). They are interconnected by brain connectors, which are veins capable of transmitting thoughts between brains. There are two important properties such a brain network should have to function properly:   It should be possible to exchange thoughts between any two pairs of brains (perhaps indirectly, through other brains).  There should be no redundant brain connectors, that is, removing any brain connector would make property 1 false. 

If both properties are satisfied, we say that the nervous system is valid. Unfortunately (?), if the system is not valid, the zombie stops thinking and becomes (even more) dead. Your task is to analyze a given nervous system of a zombie and find out whether it is valid.


-----Input-----

The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 1000) denoting the number of brains (which are conveniently numbered from 1 to n) and the number of brain connectors in the nervous system, respectively. In the next m lines, descriptions of brain connectors follow. Every connector is given as a pair of brains a b it connects (1 ≤ a, b ≤ n, a ≠ b).


-----Output-----

The output consists of one line, containing either yes or no depending on whether the nervous system is valid.


-----Examples-----
Input
4 4
1 2
2 3
3 1
4 1

Output
no

Input
6 5
1 2
2 3
3 4
4 5
3 6

Output
yes

Difficulty: interview

Starter code:

Solutions:
3

__import__("sys").setrecursionlimit(10 ** 6)

def dfs(u, tr, used):
    used[u] = True
    ans = 1
    for v in tr[u]:
        if not used[v]:
            ans += dfs(v, tr, used)
    return ans


n, m = list(map(int, input().split()))
if n != m + 1:
    print("no")
    return

tr = [[] for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    tr[a].append(b)
    tr[b].append(a)

used = [False] * n
if dfs(0, tr, used) == n:
    print("yes")
else:
    print("no")


from sys import stdin as fin
# fin = open("hcc2016c1.in", "r")

def dfs(v, p):
    nonlocal g, used, cnt
    cnt += 1
    used[v] = True
    for u in g[v]:
        if u != p and (used[u] or not dfs(u, v)):
            return False
    return True

n, m = map(int, fin.readline().split())
used = [False] * n
g = [[] for i in range(n)]
for i in range(m):
    v, u = map(int, fin.readline().split())
    v, u = v - 1, u - 1
    g[v].append(u)
    g[u].append(v)
cnt = 0
if not dfs(0, None) or cnt != n:
    print("no")
else:
    print("yes")

l = []
were = []


def dfs(v):
    nonlocal l, were
    if not were:
        were = len(l) * [False]
    were[v] = True
    for i in l[v]:
        if not were[i]:
            dfs(i)


n, m = list(map(int, input().split()))
if m != n - 1:
    print("no")
else:
    l = [[] for i in range(n)]
    for i in range(m):
        a, b = list(map(int, input().split()))
        l[a - 1].append(b - 1)
        l[b - 1].append(a - 1)

    dfs(0)
    f = True
    for i in were:
        f = f and i

    if f:
        print("yes")
    else:
        print("no")


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

def dfs(v):
    was[v] = 1
    for u in g[v]:
        if not was[u]:
            dfs(u)

was = [0] * (n + 1)
dfs(1)
ans = 'no' if 0 in was[1:] or m != n - 1 else 'yes'
print(ans)


import sys
sys.setrecursionlimit(1000000)
def dfs(v, pr):
    nonlocal used
    nonlocal p
    nonlocal f
    if not f:
        return None
    if used[v]:
        f = False
    used[v] = True
    for i in range(len(p[v])):
        if p[v][i] != pr:
            dfs(p[v][i], v)
n, m = list(map(int, input().split()))
p = []
for i in range(n):
    p.append([])
for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    p[a].append(b)
    p[b].append(a)
used = [False] * n
f = True
for i in range(n):
    if i != 0 and not used[i]:
        f = False
        break
    if not used[i]:
        dfs(i, -1)
if f:
    print('yes')
else:
    print('no')

        


n, m = list(map(int, input().split()))
ok = m == n - 1
dsu = list(range(n))
def get(x):
    y = x
    while y != dsu[y]:
        y = dsu[y]
    while x != y:
        z = dsu[x]
        dsu[x] = y
        x = z
    return y
for i in range(m):
    a, b = [int(x) - 1 for x in input().split()]
    dsu[get(a)] = get(b)
for i in range(n):
    get(i)
ok &= max(dsu) == min(dsu)
print("yes" if ok else "no")


def is_valid():
    import sys
    #with open(filename, 'r') as f:
    with sys.stdin as f:
        for i, line in enumerate(f):
            if i == 0:
                N, M = line.split(' ')
                N, M = int(N), int(M)
                if N-1 != M:
                    return False
                graph = [[] for _ in range(N)] # [[]] * N not working, no deepcopy
            else:
                fromVertex, toVertex = line.split(' ')
                fromVertex, toVertex = int(fromVertex)-1, int(toVertex)-1
                graph[fromVertex].append(toVertex)
                graph[toVertex].append(fromVertex)

    from queue import LifoQueue
    def is_single_component(start_node, graph):
        N = len(graph)
        visited = [False for _ in range(N)]
        visited[start_node] = True
        nodes_queue = LifoQueue()
        nodes_queue.put(start_node)
        while not nodes_queue.empty():
            node = nodes_queue.get()
            for neigh in graph[node]:
                if not visited[neigh]:
                    visited[neigh] = True
                    nodes_queue.put(neigh)
                #else: not a cycle because edges in both directions

        return all(visited)

    return is_single_component(0, graph)

if is_valid():
    print("yes")
else:
    print("no")

f = lambda: map(int, input().split())
n, m = f()
p = list(range(n))

def g(i):
    j = i
    while j != p[j]: j = p[j]
    while i != j: i, p[i] = p[i], j
    return j

for j in range(m):
    a, b = f()
    p[g(a - 1)] = g(b - 1)

s = g(0)
k = all(g(i) == s for i in p)

print('yes' if m == n - 1 and k else 'no')

f = lambda: map(int, input().split())
n, m = f()
p = list(range(n))

def g(i):
    while i != p[i]: i = p[i]
    return i

q = 'yes' if m == n - 1 else 'no'

for j in range(m):
    a, b = f()
    u, v = g(a - 1), g(b - 1)
    if u == v: q = 'no'
    p[u] = v

print(q)

def adds(sin,c):
    if c in sin:
        return 1
    sin.add(c)
    return 0

def corr(v,n):
    if len(v)<n-1:
        return 0
    sin={v[0][0],v[0][1]}
    v=v[1:]
    while len(v)>0:
        nv=[]
        for c in v:
            if c[0] in sin:
                if adds(sin,c[1]):
                    return 0
                continue
            if c[1] in sin:
                if adds(sin,c[0]):
                    return 0
                continue
            nv.append(c)
        if v==nv:
            return 0
        v=nv    
    if len(sin)==n:
        return 1
    else:
        return 0

n,m=list(map(int,input().split(' ')))
v=[]
for c in range(m):
    v.append(list(map(int,input().split(' '))))
if corr(v,n):
    print('yes')
else:
    print('no')


# Python program to check if a given directed graph is strongly
# connected or not
import sys
from collections import defaultdict


class Graph:
    def __init__(self, V):
        self.V = V
        self.graph = defaultdict(list)

    def addEdge(self, v, w):
        # Add w to v ist.
        self.graph[v].append(w)
        # Add v to w list.
        self.graph[w].append(v)

    # A recursive function that uses visited[]
    # and parent to detect cycle in subgraph
    # reachable from vertex v.
    def isCyclicUtil(self, v, visited, parent):

        # Mark current node as visited
        visited[v] = True

        # Recur for all the vertices adjacent
        # for this vertex
        for i in self.graph[v]:
            # If an adjacent is not visited,
            # then recur for that adjacent
            if visited[i] == False:
                if self.isCyclicUtil(i, visited, v) == True:
                    return True

            # If an adjacent is visited and not
            # parent of current vertex, then there
            # is a cycle.
            elif i != parent:
                return True

        return False

    # Returns true if the graph is a tree,
    # else false.
    def isTree(self):
        # Mark all the vertices as not visited
        # and not part of recursion stack
        visited = [False] * self.V

        # The call to isCyclicUtil serves multiple
        # purposes. It returns true if graph reachable
        # from vertex 0 is cyclcic. It also marks
        # all vertices reachable from 0.
        if self.isCyclicUtil(0, visited, -1) == True:
            return False

        # If we find a vertex which is not reachable
        # from 0 (not marked by isCyclicUtil(),
        # then we return false
        for i in range(self.V):
            if visited[i] == False:
                return False

        return True


def main():
    s = sys.stdin.readline().split()
    n, m = int(s[0]), int(s[1])
    graph = Graph(n)
    for _ in range(m):
        s = sys.stdin.readline().split()
        graph.addEdge(int(s[0]) - 1, int(s[1]) - 1)

    return "yes" if graph.isTree() else "no"


def __starting_point():
    sys.stdout.write(main())


__starting_point()

def clave(ent):
	return min(ent)
a=[int(i) for i in input().split()]
t=set(int(i) for i in input().split())
x=[]
for i in range(1,a[1]):
	x.append([int(i) for i in input().split()])
x.sort(key=clave)
while len(x):
	f=True
	for c in x:
		if (c[0] in t) + (c[1] in t)==1:
			f=False
			t.update(c)
			x.remove(c)
			break
	if f:
		print('no')		
		return
print('yes')


k=[0]*1001
def dfs(x):
    k[x]+=1
    for i in z[x]:
        if not(k[i]):dfs(i)
a,b=list(map(int,input().split()))
z=[]
for i in range(a+1):z+=[[]]
for i in range(b):
    x,y=list(map(int,input().split()))
    z[x].append(y)
    z[y].append(x)
dfs(1)
if sum(k)!=a or a-1!=b:print("no")
else:print("yes")