387_D. George and Interesting Graph
George loves graphs. Most of all, he loves interesting graphs. We will assume that a directed graph is interesting, if it meets the following criteria: 

  * The graph doesn't contain any multiple arcs; 
  * There is vertex v (we'll call her the center), such that for any vertex of graph u, the graph contains arcs (u, v) and (v, u). Please note that the graph also contains loop (v, v). 
  * The outdegree of all vertexes except for the center equals two and the indegree of all vertexes except for the center equals two. The outdegree of vertex u is the number of arcs that go out of u, the indegree of vertex u is the number of arcs that go in u. Please note that the graph can contain loops. 



However, not everything's that simple. George got a directed graph of n vertices and m arcs as a present. The graph didn't have any multiple arcs. As George loves interesting graphs, he wants to slightly alter the presented graph and transform it into an interesting one. In one alteration he can either remove an arbitrary existing arc from the graph or add an arbitrary arc to the graph. 

George wonders: what is the minimum number of changes that he needs to obtain an interesting graph from the graph he's got as a present? Help George and find the answer to the question.

Input

The first line contains two space-separated integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 1000) — the number of vertices and arcs in the presented graph.

Each of the next m lines contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ n) — the descriptions of the graph's arcs. Pair (ai, bi) means that the graph contains an arc from vertex number ai to vertex number bi. It is guaranteed that the presented graph doesn't contain multiple arcs.

Assume that the grah vertices are numbered 1 through n.

Output

Print a single integer — the answer to George's question.

Examples

Input

3 7
1 1
2 2
3 1
1 3
3 2
2 3
3 3


Output

0


Input

3 6
1 1
2 2
3 1
3 2
2 3
3 3


Output

1


Input

3 1
2 2


Output

6

Note

For more information about directed graphs, please visit: http://en.wikipedia.org/wiki/Directed_graph

In the first sample the graph already is interesting, its center is vertex 3.
```python
# by the authority of GOD     author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase

def matching(n,m,path):
    # Hopkrocft Karp O(EV^0.5)
    match1 = [-1]*n
    match2 = [-1]*m
    for node in range(n):
        for nei in path[node]:
            if match2[nei] == -1:
                match1[node] = nei
                match2[nei] = node
                break
    while 1:
        bfs = [node for node in range(n) if match1[node] == -1]
        depth = [-1]*n
        for node in bfs:
            depth[node] = 0

        for node in bfs:
            for nei in path[node]:
                next_node = match2[nei]
                if next_node == -1:
                    break
                if depth[next_node] == -1:
                    depth[next_node] = depth[node]+1
                    bfs.append(next_node)
            else:
                continue
            break
        else:
            break
        pointer = [len(c) for c in path]
        dfs = [node for node in range(n) if depth[node] == 0]
        while dfs:
            node = dfs[-1]
            while pointer[node]:
                pointer[node] -= 1
                nei = path[node][pointer[node]]
                next_node = match2[nei]
                if next_node == -1:
                    while nei != -1:
                        node = dfs.pop()
                        match2[nei],match1[node],nei = node,nei,match1[node]
                    break
                elif depth[node]+1 == depth[next_node]:
                    dfs.append(next_node)
                    break
            else:
                dfs.pop()
    return n-match1.count(-1)

def main():
    n,m = map(int,input().split())
    edg = [tuple(map(lambda xx:int(xx)-1,input().split())) for _ in range(m)]
    ans = float("inf")
    for centre in range(n):
        path = [[] for _ in range(n)]
        cost = 2*n-1
        extra = m
        for u,v in edg:
            if u == centre or v == centre:
                cost -= 1
                extra -= 1
            else:
                path[u].append(v)
        maxMatch = matching(n,n,path)
        extra -= maxMatch
        cost += n-1-maxMatch+extra
        ans = min(ans,cost)
    print(ans)

# Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
    main()
```