#include<bits/stdc++.h>

using namespace std;

bool noway[][], Gra[][];

int arr[];

int linker[];

bool used[];

bool dfs(int u, int vN) {

    for(int v = ; v <= vN; v++)

        if(Gra[u][v] && !used[v]) {

            used[v] = true;

            if(linker[v] == - || dfs(linker[v], vN)) {

                linker[v] = u;

                return true;

            }

        }

    return false;

}

int hungary(int vN) {

    int res = ;

    memset(linker,-,sizeof(linker));

    for(int u = ; u <= vN; u++) {

        memset(used,false,sizeof(used));

        if(dfs(u, vN))

            res++;

    }

    return vN - res;

}

int solve(int n) {

    memset(Gra, true, sizeof(Gra));

    for(int i = ; i <= n; i ++)

        for(int j = ; j <= n; j ++)

            if(noway[arr[i - ]][j] || noway[arr[i]][j])

                Gra[i][j] = false;

    for(int i = ; i <= n; i ++)

        if(noway[arr[]][i] || noway[arr[n]][i])

            Gra[][i] = false;

    return hungary(n);

}

int main() {

    int n,m,a,b;

    while(~scanf("%d%d",&n,&m)) {

        if(n == ){

            printf("0\n");

            continue;

        }

        memset(noway, false, sizeof(noway));

        for(int i = ; i < m; i ++) {

            scanf("%d%d",&a,&b);

            noway[b][a] = true;

        }

        int ans = ;

        for(int i = ; i <= n; i ++) arr[i] = i;

        do {

            ans = min(solve(n), ans);

        } while(next_permutation(arr + , arr + n + ));

        printf("%d\n",ans);

    }

    return ;

}