#Uses python3

import sys
import queue

def bipartite(adj):
    source = 0
    lvl = 1
    level = {source: 0}
    parent = {source: None}
    color = {source: False}
    queue = [source]
    while queue:
        # print("Current Queue: {}".format(queue))
        # print("Current Color Dict: {}".format(color))
        nextQueue = []
        for vertex in queue:
            # print("Vertex: {}".format(vertex))
            for nbr in adj[vertex]:
                # print("Neighbor: {}".format(nbr))
                if nbr not in level:
                    level[nbr] = lvl
                    parent[nbr] = vertex
                    color[nbr] = not color[vertex]
                    # print("{} not found in Level. Assigning level {}".format(nbr, lvl))
                    nextQueue.append(nbr)

                elif color[nbr] == color[vertex]:
                    # print("{} and it's parent {} have the same color".format(nbr, parent[nbr]))
                    return 0

        queue = nextQueue
        lvl += 1

    return 1

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
    adj = [[] for _ in range(n)]
    for (a, b) in edges:
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    print(bipartite(adj))
