# Uses python3

import sys
import queue


def bfsBipartiteCheck(adj, s):
    if len(adj[s]) == 0:
        return True

    dist = [-1] * len(adj)
    dist[s] = 0

    q = queue.Queue()
    q.put(s)

    while not q.empty():
        u = q.get()
        for i in adj[u]:
            if dist[i] == -1:
                q.put(i)
                if dist[u] == 0:
                    dist[i] = 1
                if dist[u] == 1:
                    dist[i] = 0
            else:
                if dist[i] == dist[u]:
                    return False
    return True


def bipartite(adj):
    bipartitite_check_nodes = bfsBipartiteCheck(adj, 0)
    if bipartitite_check_nodes:
        return 1
    else:
        return 0


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