// #pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
//#pragma GCC -Wnarrowing

//Template {
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
//IO templates
//Note: use endl only for interactive problems or to debug segfaults; use newl for other problems
#define newl "\n"
#define fastIO ios::sync_with_stdio(false); cin.tie(nullptr)
#define fileIO(x) ifstream fin((str) x + (str) ".in"); ofstream fout((str) x + (str) ".out");
// void fileIO(string x) {}
#define flush() fflush(stdout)
#define interact(n) fflush(stdout); cin >> n; if (n == -1) return 0
#define testcases int tt; cin >> tt; fun (i, tt) solve();

#define edgeIO(m) fun (i, m) {int a, b; cin >> a >> b; addEdges(a, b);}
#define WeightedEdgeIO(m) fun (i, m) {int a, b, c; cin >> a >> b >> c; addWeightedEdges(a, b, c);}
#define numberedEdgeIO(m) fun (i, m) {int a, b; cin >> a >> b; addWeightedEdges(a, b, i);}
//types
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define int long long
#define ld long double
#define str string
#define boolean bool
#define String string
 
//vector
#define pb push_back
#define append push_back
 
//pairs
#define mp make_pair
#define p2 pair<int, int>
#define p3 pair<int, p2>
#define m3(x, y, z) mp(x, mp(y, z))
#define ich first
#define ni second.first
#define sanshi second.second
 
//For loops
#define ahegao(i, a, b) for (int i = a; i < b; i++)
#define baka(i, b, a) for (int i = b; i > a; i--)
#define fun(i, n) for (int i = 1; i <= (n); (i)++)
#define fon(i, n) for (int i = 0; i < (n); (i)++)
#define fur(i, n) for (auto i : (n))
#define oniichan(i, n) for (auto &i : (n))
 
//Sorts
#define sz(aaa) ((signed) aaa.size())
// #define len(aaa) ((signed) aaa.size())
#define all(a) a.begin(), a.end()
#define Sort(a) sort((a).begin(), (a).end())
#define rSort(a) sort((a).rbegin(), (a).rend())
#define clamp(x, y) (x) = min((int) (x), (int) (y))
#define CLAMP(x, y) (x) = max((int) (x), (int) (y))
 
//Other stuff
#define pqueue priority_queue
#define elif else if
#define addEdges(a, b) adj[a].pb(b); adj[b].pb(a)
#define addWeightedEdges(a, b, c) adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c))
// #define find find_by_order
#define printLength(x) if (x < INF) cout << x << newl; else cout << -1 << newl;
// #define printVector(a) fur (i, a) cout << i << ' '; cout << newl;
void printVector(vector<int> DontUseThisName) {
    fur (i, DontUseThisName) cout << i << ' '; cout << newl;
}
void printVector(vector<p2> DontUseThisName) {
    fur (i, DontUseThisName) cout << i.first << ' ' << i.second << newl; cout << newl;
}
void printVector(vector<vector<int>> DontUseThisName) {
    fur (i, DontUseThisName) printVector(i); cout << newl;
}
ll max(ll a, signed b) {return max(a, (ll) b);}
ll max(signed a, ll b) {return max((ll) a, b);}

void pv(int a) {cout << a << newl;}
void pv(int a, int b) {printVector({a, b});}
void pv(p2 a) {printVector({a.first, a.second});};
void pv(int a, int b, int c) {printVector({a, b, c});}
void pv(int a, int b, int c, int d) {printVector({a, b, c, d});}
void pv(int a, int b, int c, int d, int e) {printVector({a, b, c, d, e});}
void pv(int a, int b, int c, int d, int e, int f) {printVector({a, b, c, d, e, f});}
// void pv(int a, )
// void printVector(vector<char> DontUseThisName) {
//     fur (i, DontUseThisName) cout << i << ' '; cout << newl;
// }
// void printRange(vector<int>::iterator Left, vector<int>::iterator Right) {
//     for (auto i = Left; i < Right; i++) cout << *i << ' ';
//     cout << newl;
// } 
//Constants
// const int MOD =  1e9+7; // 998244353
// const int SMALLMOD = 998244353;
const int INF = 2e9+1337;
const ll EXCEED = 2e18+1337;
const ll GRAVITY = 8e18;

//#define vectorIO(n, MikuBondage) fun (j, n) {int i; cin >> i; MikuBondage.pb(i);}
void vectorIO(int n, vector<int> &DontUseThisName) {
    fun (j, n) {int i; cin >> i; DontUseThisName.pb(i);}
}
//#define vector2IO(n, MikuBondage) fun (j, n) {int i, ii; cin >> i >> ii; MikuBondage.pb(mp(i, ii));}
void vector2IO(int n, vector<p2> &DontUseThisName) {
    fun (j, n) {int i, ii; cin >> i >> ii; DontUseThisName.pb(mp(i, ii));}
}

// const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
#define shortest_path_queue priority_queue<p2, vector<p2>, greater<p2>>
#define printArray(DontUseThisName, NakedLolisGalore, GenshinImpactClimbing) ahegao (j, NakedLolisGalore, GenshinImpactClimbing + 1) cout << DontUseThisName[j] << ' '; cout << newl;
#define print2dArray(SplitComplexProblemsIntoMultipleParts, ScuteSwarm, GenshinImpactClimbing) fun (i, ScuteSwarm) {fun (j, GenshinImpactClimbing) cout << SplitComplexProblemsIntoMultipleParts[i][j] << ' '; cout << newl;}
//}
const int MAX = 1003;
const int MOD = 2003;
int n, m, k, curr;
set<int> adj[MAX];
int cnt[1003];

int hash1() {
    vector<int> aaa;
    fun (i, n) {
        vector<int> temp;
        fur (j, adj[i]) temp.pb(sz(adj[j]));
        Sort(temp);
        int res = 1;
        fur (j, temp) res = (71 * res + 43 * j) % MOD;
        cnt[i] = res;
    }
    fun (i, n) {
        vector<int> temp;
        fur (j, adj[i]) temp.pb(cnt[j]);
        Sort(temp);
        int res = 1;
        fur (j, temp) res = (71 * res + j) % MOD;
        aaa.pb(res);
    }
    Sort(aaa);
    int rrr = 1;
    fur (j, aaa) rrr = (73 * rrr + j + (rrr << 5)) % MOD;
    pv(rrr);
    return rrr;
}

signed main() {
    fastIO;
    cin >> n >> m;
    // edgeIO(m);
    fun (i, m) {
        int a, b; cin >> a >> b;
        adj[a].insert(b); adj[b].insert(a);
    }
    cout << hash1() << newl;
    if (hash1() == 1337) {
        cout << "ok";
        return 0;
    }
    // return 0;
    fun (i, n) ahegao (j, i+1, n+1) {
        // hash1();
        // if (j == 100) return 0;
        if (adj[i].find(j) == adj[i].end()) {
            adj[i].insert(j);
            adj[j].insert(i);
            if (hash1() == 1337) {
                cout << "mark" << newl;
                cout << 1 << newl;
                pv(i, j);
                return 0;
            }
            adj[i].erase(j);
            adj[j].erase(i);
        }
       
    }
}