#include<fstream>
#include<vector>
using namespace std;
int viz[100001],i,n,m,con=0,k=0,coada[100001],l,t,j;
ifstream f("count.in");
ofstream g("count.out");

vector <int>A[100001];

void Citire()
{
     int i,x,y;
f>>n>>m;
   for(i=1;i<=m;i++)
   {
   f>>x>>y;
   A[x].push_back(y);
   A[y].push_back(x);                
   }
f.close();
}

   void  rareste()
   {
     for(i=1;i<=n;i++)
      if (A[i].size()<30)
	  {k++;
		  coada[k]=i;}
        
   }
      
   int vecin(int i,int j)
   {
	int k;
	    for(k=0;k<A[i].size();k++)
      if (A[i][k]==j) return 1;
		
		return 0;
   }
	
   int verific_4()
   {  
	
	   for(i=1;i<=k-3;i++)
	   
		  for(j=i+1;j<=k-2;j++)
			  if (vecin(coada[i],coada[j]))
				  for(t=j+1;t<=k-1;t++)
					  if(vecin(coada[j],coada[t]))
				for(l=t+1;l<=k;l++)
					if (vecin(coada[t],coada[l]))
                         if (vecin(coada[i],coada[t])&&vecin(coada[i],coada[l])&&vecin(coada[j],coada[l]))
						return 1;
	   
	return 0;   
   }
   int nr_4()
   {int contor=0;
      for(i=1;i<=k-3;i++)
	   
		  for(j=i+1;j<=k-2;j++)
			  if (vecin(coada[i],coada[j]))
				  for(t=j+1;t<=k-1;t++)
					  if(vecin(coada[j],coada[t]))
				for(l=t+1;l<=k;l++)
					if (vecin(coada[t],coada[l]))
 if (vecin(coada[i],coada[t])&&vecin(coada[i],coada[l])&&vecin(coada[j],coada[l]))
												contor++;
			
	return contor;
   }
   
   int verific_3()
   {  
	
	   for(i=1;i<=k-2;i++)
	   
		  for(j=i+1;j<=k-1;j++)
			  if (vecin(coada[i],coada[j]))
				  for(t=j+1;t<=k;t++)
				
					if (vecin(coada[j],coada[t])) 
							if (vecin(coada[i],coada[t])) 
				
						return 1;
	
	return 0;   
   }
   int nr_3()
   {int contor=0;
      for(i=1;i<=k-2;i++)
	   
		  for(j=i+1;j<=k-1;j++)
			  if (vecin(coada[i],coada[j]))
				  for(t=j+1;t<=k;t++)
			
					if (vecin(coada[j],coada[t])) 
						if (vecin(coada[i],coada[t])) 
				contor++;
			
	return contor;
   }
   
   
   int verific_2()
   {  
	
	   for(i=1;i<=k-1;i++)
	   
		  for(j=i+1;j<=k;j++)
					if (vecin(coada[i],coada[j])) return 1;
	   
	return 0;   
   }
   int nr_2()
   {int contor=0;
      for(i=1;i<=k-1;i++)
	   
		  for(j=i+1;j<=k;j++)
					if (vecin(coada[i],coada[j])) contor++;
			
	return contor;
   }
   
      int main()
      {
      Citire();
	  rareste();
	  if (verific_4()) g<<4<<" "<<nr_4();
	  else
		  
      if (verific_3()) g<<3<<" "<<nr_3();
	  else
	
 if (verific_2()) g<<2<<" "<<nr_2();
	
			  
      
        return 0;
   
}