#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Q=1<<19;
int ______________________________[Q],________________________________[Q<<1],_______________________________[Q<<1],_______________________=1,tt=0;
int _____________________________________[Q],fl=0;
int sid[2]={-1,-1},_______=0;
int ____________________________________[Q];
int ______________________________________[Q];
int OPSHAHAHA[12313];
int sig=0;
void _______________________________________(int ___________,int _____________,int __________________)
{
    ____________________________________[___________]=1;
    _____________________________________[___________]=__________________?1:-1;
    for(int ___=0;___<2;___++)
        if(sid[___]==___________)_____________________________________[___________]+=_______,______________________________________[___________]+=1-2*___;
    for(int _____=______________________________[___________];_____;_____=_______________________________[_____]){
        int _________=________________________________[_____];
        if(_________==_____________||(_____>>1)==tt)continue;
        if((!fl)&&____________________________________[_________]){
            tt=_____>>1;
            fl=1;
            sid[0]=___________,sid[1]=_________;
            continue;
        }
        _______________________________________(_________,___________,__________________^1);
        _____________________________________[___________]+=_____________________________________[_________];
        ______________________________________[___________]+=______________________________________[_________];
    }
    for(int ___=0;___<2;___++)
        if(sid[___]==___________)
            sig^=__________________;
}
void ins(int ___________,int _________)
{
    ________________________________[++_______________________]=_________;
    _______________________________[_______________________]=______________________________[___________];
    ______________________________[___________]=_______________________;
}
#define __________________________________________ long long
int _________________________________,__________________________________;
__________________________________________ _________________________________________(__________________________________________ a)
{return a>0?a:-a;}
void Gans(__________________________________________ ___________________________________)
{
    for(int ___=1;___<=_________________________________;___++)
        ___________________________________+=_________________________________________(_____________________________________[___]);
    cout<<___________________________________;
    exit(0);
}
int __________________________[Q];
int main()
{
    scanf("%d%d",&_________________________________,&__________________________________);
    for(int ___=1,___________,_________;___<=__________________________________;___++)
        scanf("%d%d",&___________,&_________),ins(___________,_________),ins(_________,___________);
    _______________________________________(1,0,1);
    if(__________________________________<_________________________________){
        if(_____________________________________[1])return 0&puts("-1");
        Gans(0);
    }
    if(!sig){
        if(_____________________________________[1]%2!=0)return 0&puts("-1");
        _______=-_____________________________________[1]/2;
        _______________________________________(1,0,1);
        Gans(_________________________________________(_______));
    }
    if(_____________________________________[1])return 0&puts("-1");
    _______________________________________(1,0,1);
    int tp=1;
    __________________________________________ ___________________________________=0;
    __________________________[1]=0;
    for(int ___=1;___<=_________________________________;___++)
        if(______________________________________[___])__________________________[++tp]=______________________________________[___]>0?-_____________________________________[___]:_____________________________________[___];
    nth_element(__________________________+1,__________________________+((tp+1)>>1),__________________________+tp+1);
    int ________________________________________=__________________________[(tp+1)>>1];
    for(int ___=1;___<=_________________________________;___++)
        ___________________________________+=_________________________________________(______________________________________[___]*________________________________________+_____________________________________[___]);
    cout<<___________________________________+_________________________________________(________________________________________);
    return 0;
}

Measured memory_bytes: 20736