using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
using System.IO.Pipes;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.Versioning;
using System.CodeDom;
namespace AtCoder.Abc
{
public class AtCoderABC
{
public static void Main(string[] args)
{
var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
// 実行したいクラスのMainメソッドを呼び出す
// QuestionA.Run();
// QuestionB.Run();
QuestionC.Run();
// QuestionD.Run();
// QuestionE.Run();
// QuestionF.Run();
// QuestionG.Run();
// QuestionH.Run();
// QuestionI.Run();
Console.Out.Flush();
}
}
public class QuestionA
{
public static void Run()
{
var S = Utilities.GetString();
var num = S.Length / 2;
for (int i = 0; i < S.Length; ++i)
{
if (i == num)
{
continue;
}
else
{
Console.Write(S[i]);
}
}
Console.WriteLine("");
}
}
public class QuestionB
{
public static void Run()
{
var LA = Utilities.GetLongArray();
var N = LA[0];
var A = new long[N];
long sum = 0;
long X(long x)
{
var S = x.ToString();
long ret = 0;
for (int i = 0; i < S.Length; ++i)
{
long tmp = S[i] - '0';
ret += tmp;
}
return ret;
}
for (int i = 0; i < N; ++i)
{
var tmp = i + 1;
if (i == 0)
{
A[i] = 1;
}
else
{
A[i] = (long)(X(A[i-1]) + A[i-1]);
}
sum += A[i];
}
Console.WriteLine(A[N - 1]);
}
}
public class QuestionC
{
public static void Run()
{
var LA = Utilities.GetLongArray();
var N = LA[0];
var M = LA[1];
var U = new long[M];
var V = new long[M];
for (int i = 0; i < M; ++i)
{
LA = Utilities.GetLongArray();
U[i] = LA[0] - 1;
V[i] = LA[1] - 1;
}
var COLOR = new long[N];
long minv = long.MaxValue;
for (int i = 0; i < (1 << (int)N); ++i)
{
for (int j = 0; j < N; ++j)
{
if (((i >> j) & 0x01) == 0x01)
{
COLOR[j] = 1; // 黒
}
else
{
COLOR[j] = 0; // 白
}
}
long cnt = 0;
for (int j = 0; j < M; ++j)
{
var u = U[j];
var v = V[j];
if (COLOR[u] == COLOR[v])
{
cnt++;
}
}
minv = Math.Min(minv, cnt);
}
Console.WriteLine(minv);
}
}
public class QuestionD
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionE
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionF
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionG
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionH
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionI
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
internal class Utilities
{
public static string GetString()
{
return Console.ReadLine();
}
public static long GetLong()
{
return long.Parse(Console.ReadLine());
}
public static string[] GetStringArray()
{
return Console.ReadLine().Split(' ');
}
public static long[] GetLongArray()
{
return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
}
public static void PrintArray(long[] array)
{
foreach (var item in array)
{
Console.WriteLine(item);
}
}
public static void PrintDouble(double d)
{
Console.WriteLine(string.Format("{0:f12}", d));
}
}
internal class Library
{
// Gcd（最大公約数）
public static long Gcd(long m, long n)
{
if (n == 0) return m;
return Gcd(n, m % n);
}
// Lcm（最小公倍数）答えが 10^18を超えるとき -1 を返す
public static long Lcm(long a, long b)
{
long POW18 = 1000000000000000000;
long r = a / Gcd(a, b);
if (r > (POW18 / b))
return -1;
else
return (r * b);
}
public static long Mod = 1000000007;
public static long ModPow(long a, long n)
{
long res = 1;
while (n > 0)
{
if ((n & 1) == 1)
{
res = res * a % Mod;
}
a = a * a % Mod;
n >>= 1;
}
return res;
}
public static long ModInv(long a)
{
return ModPow(a, Mod - 2);
}
public static long ModDiv(long a, long b)
{
return a * ModInv(b) % Mod;
}
public static long ModAdd(long a, long b)
{
return (a + b) % Mod;
}
public static long ModSub(long a, long b)
{
return (a - b + Mod) % Mod;
}
public static long ModMul(long a, long b)
{
return a * b % Mod;
}
public static long ModFact(long n)
{
long res = 1;
for (long i = 1; i <= n; i++)
{
res = res * i % Mod;
}
return res;
}
public static long ModComb(long n, long k)
{
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return ModFact(n) * ModInv(ModFact(k)) % Mod * ModInv(ModFact(n - k)) % Mod;
}
public static long ModPerm(long n, long k)
{
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return ModFact(n) * ModInv(ModFact(n - k)) % Mod;
}
// ダイクストラ法
// 使用例:
//int n = 5; // ノード数
//var graph = new List<(int to, long cost)>[n];
// for (int i = 0; i<n; i++)
// {
// graph[i] = new List<(int to, long cost)>();
// }
// エッジの追加 (例: ノード0からノード1へのコスト10のエッジ)
//graph[0].Add((1, 10));
//graph[0].Add((2, 3));
//graph[1].Add((2, 1));
//graph[1].Add((3, 2));
//graph[2].Add((1, 4));
//graph[2].Add((3, 8));
//graph[2].Add((4, 2));
//graph[3].Add((4, 7));
//graph[4].Add((3, 9));
// ダイクストラ法の呼び出し
//int startNode = 0; // 開始ノード
//var distances = Library.Dijkstra(n, graph, startNode);
// 結果の表示
//for (int i = 0; i<n; i++)
//{
//Console.WriteLine($"Node {i}: {distances[i]}");
//}
public static long[] Dijkstra(int n, List<(int to, long cost)>[] graph, int start)
{
var dist = new long[n];
for (int i = 0; i < n; i++) dist[i] = long.MaxValue;
dist[start] = 0;
var pq = new PriorityQueue<(long dist, int node)>();
pq.Enqueue((0, start));
while (pq.Count > 0)
{
var (d, v) = pq.Dequeue();
if (dist[v] < d) continue;
foreach (var (to, cost) in graph[v])
{
var newDist = d + cost;
if (newDist < dist[to])
{
dist[to] = newDist;
pq.Enqueue((newDist, to));
}
}
}
return dist;
}
// 優先度付きキューの実装
public class PriorityQueue<T> where T : IComparable<T>
{
private List<T> data;
public PriorityQueue()
{
this.data = new List<T>();
}
public void Enqueue(T item)
{
data.Add(item);
int ci = data.Count - 1;
while (ci > 0)
{
int pi = (ci - 1) / 2;
if (data[ci].CompareTo(data[pi]) >= 0) break;
var tmp = data[ci];
data[ci] = data[pi];
data[pi] = tmp;
ci = pi;
}
}
public T Dequeue()
{
int li = data.Count - 1;
var frontItem = data[0];
data[0] = data[li];
data.RemoveAt(li);
--li;
int pi = 0;
while (true)
{
int ci = pi * 2 + 1;
if (ci > li) break;
int rc = ci + 1;
if (rc <= li && data[rc].CompareTo(data[ci]) < 0)
ci = rc;
if (data[pi].CompareTo(data[ci]) <= 0) break;
var tmp = data[pi];
data[pi] = data[ci];
data[ci] = tmp;
pi = ci;
}
return frontItem;
}
public int Count => data.Count;
}
// Union-Find Treeの実装
public class UnionFind
{
private int[] parent;
private int[] rank;
private int[] size;
public UnionFind(int n)
{
parent = new int[n];
rank = new int[n];
size = new int[n];
for (int i = 0; i < n; i++)
{
parent[i] = i;
rank[i] = 0;
size[i] = 1;
}
}
public int Find(int x)
{
if (parent[x] == x)
{
return x;
}
else
{
parent[x] = Find(parent[x]);
return parent[x];
}
}
public void Union(int x, int y)
{
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY)
{
if (rank[rootX] < rank[rootY])
{
parent[rootX] = rootY;
size[rootY] += size[rootX];
}
else if (rank[rootX] > rank[rootY])
{
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
else
{
parent[rootY] = rootX;
size[rootX] += size[rootY];
rank[rootX]++;
}
}
}
public bool Same(int x, int y)
{
return Find(x) == Find(y);
}
public int Size(int x)
{
return size[Find(x)];
}
public int CountGroups()
{
int count = 0;
for (int i = 0; i < parent.Length; i++)
{
if (parent[i] == i)
{
count++;
}
}
return count;
}
}
}
}