#include <fstream>
#define Nmax 10000
using namespace std;

ifstream fin("ciclueuler.in");//pentru ca un graf sa fie eulerian el trebuie sa fie conex si gradul fiecarei 
ofstream fout("ciclueuler.out");

int n,m;
int a[Nmax][Nmax];
int viz[Nmax];

void citire();
void euler();
void dfs(int x);//returneaza daca graful este conex

void citire(){
	int i,j,contor;
	fin>>n>>m;
	for(contor=1;contor<=m;contor++){
		fin>>i>>j;
		a[i][j]=1;
		a[j][i]=1;
	}
}

void dfs(int x){
	int j;
	viz[x]=1;
	for(j=1;j<=n;j++)
		if(a[x][j]==1 &&viz[j]==0)
			dfs(j);
}

void euler(){
	int i,j,grad,par=1,conex=1;
	//aplicam dfs
	dfs(1);
	for(i=1;i<=n;i++)
		if(viz[i]!=1)//exista un vf neparcurs
			conex=0;
	if(conex==1)//graful este conex
		for(i=1;i<=n &&par==1;i++){
			grad=0;
			for(j=1;j<=n;j++)
				if(a[i][j]==1)
					grad++;
			if(grad%2!=0)//gradul este impar
				par=0;
		}
		if(par==1&&conex==1)
			fout<<"Graful este eulerian";
		else
			fout<<"-1";
}

int main(){
	citire();
	euler();
	fout.close();
	return 0;
}