#include <fstream>
#include <vector>
#define N 100005
#define M 666013
using namespace std;
ifstream fin("gasti.in");
ofstream fout("gasti.out");

vector <int> G[N];
int n, m;

int Gasti[N], Membri[N], Cate[N];
int cnt;
void DFS(int node, int gasca)
{
    cnt++;
    Gasti[node]=gasca;
    vector<int> :: iterator it;
    for(it=G[node].begin(); it!=G[node].end(); ++it)
    {
        if(!Gasti[*it]) DFS(*it, gasca);
    }
}

int main()
{
  fin>>n>>m;
  for(int i=1;i<=m;++i)
  {
      int x,y;
      fin>>x>>y;
      G[x].push_back(y);
      G[y].push_back(x);
  }
  int gasti=0, max1=-1, max2=-1;
  for(int i=1;i<=n;++i)
  {
     if(!Gasti[i])
     {
         cnt=0;
         DFS(i,++gasti);
         Membri[gasti]=cnt;
         Cate[Membri[gasti]]++;
         if(Membri[gasti]>max1){
            max2=max1;
            max1=Membri[gasti];
         }
         else if(Membri[gasti]>max2)
              max2=Membri[gasti];
     }
  }
  long long x,y;
  if(max1!=max2)
  {
      x=(Cate[max1]*max1)% M;
      y=(Cate[max2]*max2)% M;
  }
  else
  {
      x=(max1*max2)%M;
      y=(Cate[max1]*(Cate[max1]-1)/2)% M;
  }
  x=(x*y)%M;
  fout<<gasti<<" "<<x;
  return 0;
}