import sys


class Matrix():
    """ A square matrix with n by n elements """

    def __init__(self, n, A=None):
        if A is None:
            A = [n * [0] for _ in range(n)]
        self.A = A
        self.n = n
    
    def set(self, i, j, val):
        """ sets A_ij to val """
        self.A[i][j] = val
    
    def get(self, i, j):
        """ returns the value of the A_ij  """
        return self.A[i][j]

    def copy(self):
        """ returns a deep copy of the matrix """
        A = [l.copy() for l in self.A]
        return Matrix(self.n, A=A)

    def __repr__(self):
        return f'<Matrix n:{self.n}>'

    def __str__(self):
        s = '   ' + ' '.join([str(i) for i in range(self.n)]) + ' \n'
        s += '  --' + (2 * self.n) * '-' + '\n'
        for i, row in enumerate(self.A):
            s += f'{i} |'
            for col in row:
                s += str(col) + ' '
            s += '|\n'
        s += '  --' + (2 * self.n) * '-' + '\n'
        return s


class BipartiteGraph():
    """
    A bipartite graph with as many edges on each side. The source has index 0,
    the sink has index (n + 1). The vertices in U have index 1 to n, and in V
    have index n + 1 to 2n.
    """

    def __init__(self, n, adj=None, weights=None):
        """
        Initializes a bipartite graph with n vertices on each side and no edges
        """
        if adj is None:
            adj = Matrix(2*n + 2)
        if weights is None:
            weights = Matrix(2*n + 2)
        self.n = n
        self.adj_matrix = adj
        self.weight_matrix = weights
        source = 0
        # Connect Source with weight 2
        for ui in range(1, self.n+1):
            self.adj_matrix.set(source, ui, 1)
            self.weight_matrix.set(source, ui, 2)
        # Connect Sink with weight 2
        sink = (2 * self.n) + 1
        for i in range(self.n+1, 2*self.n + 1):
            self.adj_matrix.set(i, sink, 1)
            self.weight_matrix.set(i, sink, 2)

    def add_edge(self, u, v, w=1):
        """ Add an edge from u to v with weight w. """
        self.adj_matrix.set(u, v, 1)
        self.weight_matrix.set(u, v, w)

    def get_weight(self, u, v):
        """ return: int. the weight of the edge (u, v) """
        if self.adj_matrix.get(u, v) == 1:
            return self.weight_matrix.get(u, v)
        else:
            return None
                
    def get_adjacency_list(self, u):
        """ return: list(int). the list of vertices that are adjacent to u """
        return [i for i, val in enumerate(self.adj_matrix.A[u]) if val == 1]

    def get_adjacency_matrix(self):
        """ return: Matrix(n). The adjacency matrix for this graph """
        return self.adj_matrix

    def set_weight(self, u, v, w):
        """ sets the weight of edge (u, v) to w. """
        if self.adj_matrix.get(u, v) == 1:
            self.weight_matrix.set(u, v, w)

    def residual_network(self, flow):
        """
        Computes the residual network for the graph.
        Does not copy the adj matrix (for performance reasons) so don't modify
        its values in the residual network if you need to use it again.

        param flow: Matrix(2n + 2)
        return: BipartiteGraph. The residual network
        """
        residual_weights = Matrix(2 * self.n + 2)
        # Compute residual network from s <-> ui
        source = 0
        for i in range(self.n + 1):
            f = flow.get(source, i)
            c = self.weight_matrix.get(source, i)
            res_flow = c - f
            if res_flow > 0:
                residual_weights.set(source, i, res_flow)
            if f > 0:
                residual_weights.set(i, source, f)

        # Compute residual network from ui <-> vj
        source = 0
        for ui in range(1, self.n + 1):
            for vj in range(self.n + 1, 2*self.n + 1):
                f = flow.get(ui, vj)
                c = self.weight_matrix.get(ui, vj)
                res_flow = c - f
                if res_flow > 0:
                    residual_weights.set(ui, vj, res_flow)
                if f > 0:
                    residual_weights.set(vj, ui, f)

        # Compute residual network from vj <-> t
        sink = 2 * self.n + 1
        for i in range(self.n + 1, 2*self.n + 1):
            f = flow.get(i, sink)
            c = self.weight_matrix.get(i, sink)
            res_flow = c - f
            if res_flow > 0:
                residual_weights.set(i, sink, res_flow)
            if f > 0:
                residual_weights.set(sink, i, f)
        return BipartiteGraph(self.n, adj=self.adj_matrix, weights=residual_weights)


    def copy(self, zero_weights=True):
        """
        If zero_weights, all weights are set to 0 (including the ones
        connecting the source and sink).

        return: BipartiteGraph. A copy of this graph.
        """
        adj_mat = self.adj_matrix.copy()
        if zero_weights:
            weight_mat = Matrix(self.n + 2)
        else:
            weight_mat = self.weight_matrix.copy()
        return BipartiteGraph(self.n, adj=adj_mat, weights=weight_mat)

    def __repr__(self):
        return f'<BipartiteGraph n:{self.n}>'


def read_inputs():
    """
    Reads the input to the program from stdin.
    Computes the adjacency matrix A for the graph
    
    returns: n, m, A
    """
    n, m = [int(v) for v in sys.stdin.readline().split(' ')]

    A = Matrix(n)

    for i in range(m):
        ui, vi = [int(v) for v in sys.stdin.readline().split(' ')]
        A.set(ui, vi, 1)

    return n, m, A

"""
BFS takes a BipartiteGraph, a starting node and returns a path.
Path is empty if there is no connection between source and destination vertices
"""
def bfs2(residual_graph):
    source = 0
    sink = 2 * residual_graph.n + 1

    path = {}

    # for each node, path[node] = parent
    queue = [source]
    visited = set([source])
    
    while len(queue) > 0:
        # pop first node from the queue
        curr_node = queue.pop(0)
        for neighbour in residual_graph.get_adjacency_list(curr_node):
            if neighbour not in visited and residual_graph.get_weight(curr_node, neighbour) > 0:
                queue.append(neighbour)
                path[neighbour] = curr_node
                visited.add(neighbour)

    # compute shortest path to sink, if one was found
    path_found = None
    if (sink in visited):
        p = sink
        path_found = [sink]
        while path.get(p) is not None and path.get(p) != source:
            p = path.get(p)
            path_found = [p] + path_found

        path_found = [source] + path_found
    
    # return true if we reached sink from source else false
    # and the list of nodes to follow from source to sink
    return (sink in visited), path_found


def example_bfs():
    n = 3
    g = BipartiteGraph(n=n)
    g.add_edge(1, n + 1)
    g.add_edge(2, n + 2)
    g.add_edge(2, n + 3)
    g.add_edge(3, n + 3)
    print(f'Graph: {g}')
    print('Adjacency Matrix:')
    print(g.adj_matrix)
    print('Weight Matrix:')
    print(g.weight_matrix)

    flow = Matrix(2 * n + 2)
    residual = g.residual_network(flow)
    print('\n\n\n')
    print('Residual Graph:')
    print(residual.adj_matrix)
    print(residual.weight_matrix)

    print('\n\n\n')
    print('BFS:')
    found, path = bfs(residual)

    print(' -> '.join([str(v) for v in path]))
    

def read_inputs():
    """
    Reads the input to the program from stdin.
    Computes the adjacency matrix A for the graph
    
    returns: n, m, A
    """
    n, m = [int(v) for v in sys.stdin.readline().split(' ')]

    A = Matrix(n)

    for i in range(m):
        ui, vi = [int(v) for v in sys.stdin.readline().split(' ')]
        A.set(ui, vi, 1)

    return n, m, A
    

def ford_fulkerson(g):
    flow = Matrix(2 * n + 2)
    residual = g.residual_network(flow)
    pathExists, path = bfs2(residual)
    source = 0
    max_flow=0
    while(pathExists){
        curr_node = source #=0
        path_capacity = sys.maxsize
        for neighbour in path:
            nc = residual_graph.get_weight(curr_node, neighbour)
            path_capacity = min(path_capacity,nc)
            curr_node = neighbour
        max_flow +=path_capacity
        
        curr_node = source #=0
        for neighbour in path:
            f_uv = flow.get(curr_node, neighbour)
            f_vu = flow.get(neighbour, curr_node)
            flow.set(curr_node, neighbour,f_uv + path_capacity)
            flow.set(neighbour, curr_node,f_vu + path_capacity)
            
        pathExists, path = bfs2(residual)
        residual = g.residual_network(flow)
    
    }
    return max_flow
    
    
    
""" BFS takes a BipartiteGraph, a starting node and returns a path. Path is empty if there is no connection between source and destination vertices""""
def bfs(graph, residual_graph, path, source, dest):
    # for each node, path[node] = parent
    queue = [source]
    visited = set(source)
    
    while len(queue) > 0:
        #pop first node from the queue
        curr_node = queue.pop(0)
        for neighbour in graph.adjacencyList(curr_node):
            if neighbour not in explored and residual_graph[curr_node][neighbour] > 0:
                queue.append(neigbour)
                path[neighbour] = current_node
                visited.add(neighbour)
    #return true if we reached sink from source else false
    return visited.get(dest,False)