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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001001001001ll;

struct BinaryIndexedTree{
    int n;
    vector<int>dat;
    BinaryIndexedTree(int n=0):n(n){
        dat.resize(n+1);
    }
    void add(int k,int x){
        for(k++;k<=n;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};

int N,M;
vint G[111111];

namespace S1{
    int num[111111];
    int sz[111111];
    int ans=0;
    void dfs(int v,int p,int c){
        num[v]=c;
        sz[v]=1;
        for(auto u:G[v]){
            if(u==p)continue;
            dfs(u,v,1-c);
            num[v]+=num[u];
            sz[v]+=sz[u];
        }
        ans+=abs(sz[v]-num[v]*2);
    }
    void solve(){
        dfs(0,-1,0);
        if(num[0]*2!=N)cout<<-1<<endl;
        else cout<<ans<<endl;
    }
}

vint T[111111];
vint C;

namespace S2{
    int num[111111];
    int sz[111111];
    int ans=0;
    void dfs(int v,int p,int c){
        num[v]=c;
        sz[v]=1;
        for(auto u:T[v]){
            if(u==p)continue;
            dfs(u,v,1-c);
            num[v]+=num[u];
            sz[v]+=sz[u];
        }
        if(p!=-1)ans+=abs(sz[v]-num[v]*2);
    }

    void solve(){
        int n=C.size();
        vint A(n);
        rep(i,C.size()){
            dfs(C[i],-1,i&1);
            A[i]=sz[C[i]]-num[C[i]]*2;
        }

        if(n&1){

            int tmp=accumulate(all(A),0ll);
            if(tmp%2!=0){
                cout<<-1<<endl;
                return;
            }
            tmp/=2;
            A[0]-=tmp;
            A.back()-=tmp;
            ans+=abs(tmp);
            int sum=0;
            rep(i,A.size()){
                sum+=A[i];
                ans+=abs(sum);
            }
            cout<<ans<<endl;
            return;
        }

        if(accumulate(all(A),0ll)!=0){
            cout<<-1<<endl;
            return;
        }
        
        vint sum(2*n+1);
        rep(i,2*n){
            sum[i+1]=sum[i]+A[i%n];
        }
        BinaryIndexedTree bit(1000000);
        BinaryIndexedTree bitnum(1000000);
        rep(i,n-1){
            bit.add(500000+sum[i+1],sum[i+1]);
            bitnum.add(500000+sum[i+1],1);
        }
        int mi=INF;
        for(int i=0;i<n;i++){
            bit.add(500000+sum[i+n],sum[i+n]);
            bitnum.add(500000+sum[i+n],1);

            int foo=bit.sum(1000000)-bit.sum(sum[i]+500000);
            int bar=n-bitnum.sum(sum[i]+500000);
            int tmp=0;
            tmp+=foo-bar*sum[i];

            foo=bit.sum(sum[i]+500000);
            bar=bitnum.sum(sum[i]+500000);
            tmp+=bar*sum[i]-foo;
            chmin(mi,tmp);
            bit.add(500000+sum[i+1],-sum[i+1]);
            bitnum.add(500000+sum[i+1],-1);
        }
        cout<<ans+mi<<endl;


    }
}

signed main(){
    cin>>N>>M;
    rep(i,M){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }
    if(M==N-1){
        S1::solve();
        return 0;
    }
    vint deg(N);
    rep(i,N)for(auto u:G[i])deg[u]++;
    queue<int>que;
    rep(i,N)if(deg[i]==1)que.push(i);
    while(que.size()){
        int v=que.front();
        que.pop();
        for(auto u:G[v]){
            deg[u]--;
            if(deg[u]>=1)T[u].pb(v);
            if(deg[u]==1)que.push(u);
        }
    }
    int v;
    rep(i,N)if(deg[i]==2)v=i;
    while(true){
        C.pb(v);
        deg[v]=-1;
        int k=-1;
        for(auto u:G[v])if(deg[u]==2)k=u;
        if(k==-1)break;
        v=k;
    }

    S2::solve();
    return 0;
}


Measured memory_bytes: 31740