#include <bits/stdc++.h>
using namespace std;
ifstream f("count.in");
ofstream g("count.out");
int n,m,x,y,i,S[5],F[30010];
queue<short> Q;
set<short> G[30010];
set<short>::iterator a,b,c,sf;
bool ok(int a,int b) {  return a!=b&&G[a].find(b)!=G[a].end();  }
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        G[x].insert(y);
        G[y].insert(x);
        F[x]++;
        F[y]++;
    }
    for(i=1;i<=n;++i)
        if(F[i]<6) Q.push(i);
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for(a=G[x].begin(),sf=G[x].end();a!=sf;++a)
            for(b=a;b!=sf;++b)
                if(ok(*a,*b))
                    for(c=b,S[3]++;c!=sf;++c)
                        S[4]+=(ok(*a,*c)&&ok(*b,*c));
        for(a=G[x].begin();a!=sf;++a)
        {
            G[*a].erase(x);
            if(--F[*a]==5) Q.push(*a);
        }
    }
    S[2]=m;
    for(i=4;i;--i)
        if(S[i]) g<<i<<' '<<S[i],i=1;
    return 0;
}