#include "stdio.h"
#define fin  "iepuri.in"
#define fout "iepuri.out"
#define mod 30011

    struct nod
    {
        int x;
        nod* next;
    };

    int n,k,dpt=0,tata[101],depth[101],poz[101];
    nod* G[101];
    int rez,root;
    int viz[101];

void add(int a,int b)
{
    if (a>dpt)
        dpt=a;
    tata[b]=a;
    nod* p=new nod;
    p->x = b;
    p->next=G[a];
    G[a]=p;
}

void citire()
{
    freopen(fin,"r",stdin);
    scanf("%d %d",&n,&k);
    int a,b;
    while (scanf("%d %d",&a,&b)>0)
    {
        viz[a]=0; viz[b]=0;
        add(a,b);
    }
}

void dfs(int y,int x,int k)
{
    if (depth[y]<k)
        depth[y]=k;
    for (nod* p=G[x];p;p=p->next)
    if (!viz[p->x])
    {
        viz[p->x]=1;
        dfs(y,p->x,k+1);
    }
}

void calc()
{
    rez=1;
    for (int i=1;i<=n;i++)
    {
        if (!depth[i])
        {
	    for (int j=1;j<=n;viz[j]=0,j++);
            dfs(i,i,0);
        }
	rez=((rez)*((k-depth[i]-poz[i]+1)));
    }
}

void get_poz(int i)
{
    for (nod* p=G[i];p;p=p->next)
    if (!viz[p->x])
    {
	viz[p->x]=1;
        poz[p->x]=poz[i]+1;
        get_poz(p->x);
    }
}

int main()
{
    citire();
    int bl=1;
    for (int i=1;i<=n&&bl;i++)
        if (tata[i]==0)
        {
            root=i;
	    bl=0;
        }
    poz[root]=1;
    get_poz(root);
    calc();
    freopen(fout,"w",stdout);
        printf("%d ",rez);
    fclose(stdout);
    return 0;
}