#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl







const int maxn = 18;
const int inf = 1e9;

int n, m;
bool g[maxn][maxn];
bool f[1<<maxn]; //true if mask is a clique

int dp[1<<maxn]; //min CC's

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    for (int i=0; i<m; i++) {
	int u,v; cin>>u>>v;
	--u; --v;
	g[u][v]=g[v][u]=true;
    }

    f[0] = true;
    
    for (int mask=1; mask<1<<n; mask++) {
	if (__builtin_popcount(mask) == 1) {
	    f[mask] = true;
	    continue;
	}

	for (int j=0; j<n; j++) {
	    if (mask>>j&1) {
		int pmask = (mask^(1<<j));
		if (f[pmask]) {
		    bool ok = true;
		    for (int k=0; k<n && ok; k++) {
			if (pmask>>k&1) {
			    ok &= g[j][k];
			}
		    }

		    if (ok) {
			f[mask] = true;
			break;
		    }
		}
	    }
	}
    }


    dp[0] = 0;
    for (int mask=1; mask<(1<<n); mask++) {
	dp[mask] = inf;
	for (int s=mask;;s=(s-1)&mask) {
	    if (f[s]) {
		dp[mask] = min(dp[mask], 1+dp[mask^s]);
	    }
	    if (s==0) break;
	}
    }


    int res = dp[(1<<n)-1];
    out(res);
    
    return 0;
}

/*________________________________Author : mr_robot101_________________________________*/

#include <bits/stdc++.h>
using namespace std;

/*_____________________________________________________________________________________*/

#define gc getchar_unlocked
#define fo(i, n) for (int i = 0; i < n; i++)
#define Fo(i, k, n) for (int i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
#define ll long long int
#define ull unsigned long long int
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x, val) memset(x, (int)val, sizeof(x))
#define sortall(x) sort(all(x))
#define sortrev(x) sort(all(x), greater<int>())
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define print(a)          \
	for (auto i : a)      \
		cout << i << " "; \
	cout << endl;
#define setbits(x) _builtin_popcount(x)
#define parity(x) _builtin_parity(x)
#define leadzero(x) __builtin_clz(x)
#define trailizero(x) __builtin_ctz(x)
#define endl "\n"
#define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define CHRONO srand(chrono::high_resolution_clock::now().time_since_epoch().count())

/*_____________________________________________________________________________________*/

typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef map<int, int> mii;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim)
{
	uniform_int_distribution<int> uid(0, lim - 1);
	return uid(rang);
}
void yes() { cout << "Yes\n"; }
void no() { cout << "No\n"; }
const int INF = 1e9;
ll mod = 1e9 + 7;
const int N = 1e6 + 1, M = N;

/*_____________________________________________________________________________________*/
struct segTree {
	int size;
	vector<long long> sums;
	void init(int n) {
		size = 1;
		while (size < n)   size *= 2;
		sums.assign(2 * size, 0LL);
	}

	void build(vector<int> &a, int x, int lx, int rx) {
		if (rx - lx == 1) {
			if (lx < (int)a.size()) {
				sums[x] = a[lx];
			}
			return;
		}
		int m = (lx + rx) / 2;
		build(a, 2 * x + 1, lx, m);
		build(a, 2 * x + 2, m, rx);
		sums[x] = sums[2 * x + 1] ^ sums[2 * x + 2];
	}

	void build(vector<int> &a) {
		build(a, 0, 0, size);
	}

	void set(int i, int v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			sums[x] ^= v;
			return;
		}
		int m = (lx + rx) / 2;
		if (i < m) {
			set(i, v, 2 * x + 1, lx, m);
		}
		else set(i, v, 2 * x + 2, m, rx);
		sums[x] = sums[2 * x + 1] ^ sums[2 * x + 2];
	}

	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}

	long long sum(int l, int r, int x, int lx, int rx) {
		if (lx >= r || l >= rx) return 0;
		if (lx >= l && rx <= r)  return sums[x];
		int m = (lx + rx) / 2;
		auto v1 = sum(l , r, 2 * x + 1, lx, m);
		auto v2 = sum(l, r, 2 * x + 2, m, rx);
		return v1 ^ v2;
	}

	long long sum(int l, int r) {
		return sum(l, r, 0, 0, size);
	}
};



void solve()
{
	int dp[1005][1005];
	// dp[n][m]
	int n, m;
	cin >> n >> m;
	vi a(n), b(m);
	fo(i, n)	cin >> a[i];
	fo(i, m)	cin >> b[i];
	fo(i, n + 1)	dp[i][0] = i;
	fo(i, m + 1)	dp[0][i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (a[i - 1] != b[j - 1])});
		}
	}
	cout << dp[n][m];
}

/*_____________________________________________________________________________________*/

int32_t main()
{
	FAST;
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

/*_____________________________________________________________________________________*/
