using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int lineCount = int.Parse(Reader.ReadLine());
        int inputCount = int.Parse(Reader.ReadLine());

        int[] dic = new int[lineCount];

        List<int> numList = new List<int>();
        int ans = lineCount;
        for (int i = 1; i <= lineCount; i++)
        {
            numList.Add(i-1);
        }

        List<AmidaLine> amidaList = new List<AmidaLine>();
        for (int i = 0; i < inputCount; i++)
        {
            int[] inpt = Reader.GetInt();
            AmidaLine al = new AmidaLine(inpt[0]-1, inpt[1]-1, i);
            amidaList.Add(al);
        }

        for (int i = 0; i < lineCount; i++)
        {
            int pos = -1;
            int idx = i;
            for (int j = 0; j < inputCount; j++)
            {
                List<AmidaLine> select = new List<AmidaLine>(amidaList.FindAll(a => (a.Line1 == idx || a.Line2 == idx) && a.Pos > pos).OrderBy(b => b.Pos));
                if (select.Count == 0)
                {
                    break;
                }
                pos = select[0].Pos;
                idx = select[0].Goto(idx);
            }
            dic[i] = idx;
        }

        int[] target = numList.ToArray();
        int[] conv = new int[target.Length];
        for (int i = 0; i < int.MaxValue; i++)
        {
            conv = new int[target.Length];
            bool isMatch = true;
            for (int j = 0; j < target.Length; j++)
            {
                conv[dic[j]] = target[j];
                if (isMatch && dic[j] != target[j])
                {
                    isMatch = false;
                }
            }
            target = conv;
            if (isMatch)
            {
                ans = i + 1;
                break;
            }

        }
        Console.WriteLine(ans);

    }


    public class AmidaLine
    {
        public int Line1;
        public int Line2;
        public int Pos;
        public int Goto(int from)
        {
            if (from == Line1)
            {
                return Line2;
            }
            return Line1;
        }
        public AmidaLine(int l1, int l2, int p)
        {
            this.Line2 = l2;
            this.Line1 = l1;
            this.Pos = p;
        }
    }


    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"






100
449
99 100
89 90
71 72
7 8
9 10
92 93
7 8
80 81
96 97
31 32
62 63
13 14
29 30
16 17
35 36
96 97
23 24
37 38
54 55
88 89
31 32
38 39
88 89
63 64
68 69
95 96
1 2
13 14
4 5
2 3
34 35
13 14
14 15
93 94
60 61
46 47
90 91
2 3
26 27
79 80
65 66
47 48
40 41
69 70
34 35
90 91
96 97
15 16
31 32
55 56
96 97
48 49
27 28
79 80
26 27
58 59
1 2
84 85
4 5
14 15
81 82
34 35
67 68
89 90
80 81
6 7
26 27
91 92
8 9
95 96
91 92
21 22
92 93
82 83
61 62
98 99
7 8
40 41
37 38
31 32
23 24
94 95
60 61
52 53
82 83
77 78
90 91
84 85
58 59
47 48
90 91
43 44
26 27
78 79
30 31
50 51
95 96
39 40
15 16
70 71
35 36
67 68
58 59
1 2
50 51
15 16
99 100
18 19
38 39
66 67
91 92
10 11
19 20
16 17
66 67
63 64
45 46
70 71
56 57
58 59
71 72
37 38
94 95
43 44
73 74
99 100
83 84
36 37
54 55
17 18
27 28
69 70
45 46
14 15
22 23
92 93
71 72
27 28
35 36
2 3
63 64
51 52
63 64
10 11
27 28
16 17
25 26
91 92
77 78
98 99
32 33
5 6
33 34
70 71
63 64
71 72
33 34
38 39
16 17
1 2
72 73
22 23
19 20
24 25
23 24
90 91
96 97
65 66
45 46
97 98
13 14
87 88
12 13
58 59
19 20
91 92
21 22
56 57
8 9
55 56
52 53
35 36
58 59
57 58
87 88
87 88
6 7
6 7
94 95
61 62
30 31
40 41
18 19
82 83
15 16
36 37
99 100
64 65
68 69
22 23
67 68
82 83
17 18
25 26
19 20
65 66
68 69
40 41
40 41
73 74
97 98
43 44
38 39
80 81
67 68
11 12
84 85
8 9
9 10
81 82
93 94
58 59
83 84
87 88
69 70
97 98
54 55
98 99
51 52
3 4
94 95
21 22
25 26
80 81
24 25
35 36
73 74
37 38
32 33
54 55
37 38
3 4
15 16
87 88
38 39
34 35
32 33
98 99
96 97
98 99
37 38
92 93
6 7
61 62
81 82
91 92
78 79
27 28
87 88
31 32
15 16
22 23
44 45
2 3
48 49
61 62
44 45
89 90
13 14
22 23
40 41
64 65
78 79
77 78
80 81
38 39
42 43
40 41
47 48
46 47
73 74
60 61
76 77
71 72
57 58
95 96
95 96
8 9
27 28
97 98
69 70
28 29
49 50
37 38
69 70
79 80
12 13
90 91
51 52
86 87
75 76
74 75
9 10
42 43
59 60
53 54
31 32
19 20
31 32
62 63
5 6
76 77
95 96
39 40
77 78
56 57
32 33
60 61
83 84
93 94
58 59
3 4
65 66
41 42
14 15
84 85
87 88
63 64
61 62
81 82
8 9
50 51
60 61
17 18
37 38
56 57
89 90
8 9
84 85
4 5
75 76
47 48
82 83
92 93
20 21
48 49
85 86
57 58
26 27
44 45
44 45
42 43
68 69
70 71
29 30
14 15
32 33
10 11
64 65
45 46
13 14
94 95
71 72
64 65
59 60
34 35
15 16
54 55
10 11
77 78
80 81
44 45
62 63
9 10
95 96
9 10
23 24
30 31
87 88
89 90
29 30
62 63
7 8
17 18
68 69
73 74
73 74
83 84
50 51
45 46
81 82
47 48
89 90
61 62
28 29
51 52
36 37
49 50
28 29
84 85
14 15
56 57
80 81
80 81
91 92
60 61
62 63
76 77
27 28
70 71
15 16
8 9
49 50
25 26
21 22
44 45
59 60
91 92
72 73
30 31
8 9
8 9
83 84
48 49
18 19
16 17
1 2
32 33
48 49
37 38
66 67
23 24
44 45
27 28
67 68
85 86
14 15
48 49
82 83
4 5
56 57
64 65
36 37
21 22
97 98
4 5
91 92
16 17
56 57



 
";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        public static int[] GetInt(char delimiter = ' ', bool trim = false)
        {
            string inptStr = ReadLine();
            if (trim)
            {
                inptStr = inptStr.Trim();
            }
            string[] inpt = inptStr.Split(delimiter);
            int[] ret = new int[inpt.Length];
            for (int i = 0; i < inpt.Length; i++)
            {
                ret[i] = int.Parse(inpt[i]);
            }
            return ret;
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}