#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int n,m,a[20][20],ok[300000],dp[300000];

int main()
{
  cin>>n>>m;
  int x,y;
  rep(i,m)
  {
    scanf("%d%d",&x,&y);
    --x;
    --y;
    a[x][y]=a[y][x]=1;
  }
  rep(i,1<<n)
  {
    bool b=true;
    rep(j,n) 
    {
      for(int k=j+1;k<n;k++)
      {
        if((i&(1<<j))==0||(i&(1<<k))==0) continue;
        if(a[j][k]==0)
        {
          b=false;
          break;
        }
      }
      if(!b) break;
    }
    ok[i]=(int)b;
  }
  rep(i,(1<<n)+5) dp[i]=1e9;
  dp[0]=0;
  rep(i,1<<n)
  {
    if(dp[i]==1e9) continue;
    int lft=(1<<n)-1-i;
    for(int sub=lft;sub>0;sub=(sub-1)&lft) if(ok[sub]==1) dp[i|sub]=min(dp[i|sub],dp[i]+1);
  }
  cout<<dp[(1<<n)-1]<<endl;
	return 0;
}
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
#include <functional>
#include <numeric>
using namespace std;
typedef long long ll;

#define fi first
#define se second
#define debugA cerr << "AAAAA" << endl
#define debug_ cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    cout << #v << endl;                \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;
#define debug_vec2(v)                         \
    cout << #v << endl;                       \
    for (int i = 0; i < v.size(); i++)        \
    {                                         \
        for (int j = 0; j < v[i].size(); j++) \
        {                                     \
            cout << v[i][j] << " ";           \
        }                                     \
        cout << endl;                         \
    }

template <typename T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmin(T &a, const T &b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
void quit(T a)
{
    cout << a << endl;
    exit(0);
}

using Graph = vector<vector<int> >;
using P = pair<int, int>;
using P1 = pair<int, pair<int, int> >; // クラスカル法とかで、{cost, {from,
                                      // to}}的に使う。
const ll LINF = 10010020030040056ll;
const int INF = 1001001001;
const double pi = acos(-1);


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    ll n, m;
    cin >> n >> m;
    if(n == 1){
        if(m == 0){
            cout << 1 << " " << 2 << endl;
            return 0;
        }
        else{
            cout << -1 << endl;
            return 0;
        }
    }
    if(abs(m) >= n-1){
        cout << "-1" << endl;
        return 0;
    }
    if(m == 0){
        ll tmp = 1;
        for(int i=0;i<n;i++){
            cout << tmp << " ";
            tmp++;
            cout << tmp << endl;
            tmp++;
        }
        return 0;
    }
    if(m > 0){
        ll tmp = 0;
        for(int i=0;i<m+1;i++){
            cout << n-m+2*i << " " << n-m+2*i+1 << endl;
            tmp = n-m+2*i+1;
        }
        for(int i=0;i<n-m-1;i++){
            tmp++;
            cout << n-m-1-i << " " << tmp << endl;
        }
    }
    else{
        cout << "-1" << endl;
    }

    return 0;
}
