using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
 
namespace Кол_во_циклов_в_графе_1_
{
    class Program
    {
        public static int vertex_count;
        public static int edge_count; 
        public static int[,] Graph;
        public static int Amount = 0;
        public static int[] cnt;
 
        static void Main(string[] args)
        {
            int n1, n2; 
            string[] lines = File.ReadAllLines("graph.txt");
            string[] str = lines[0].Split(' ');
            vertex_count = Int32.Parse(str[0]);
            edge_count = Int32.Parse(str[1]);
 
            Graph = new int[vertex_count, edge_count];
 
            for (int k = 1; k < lines.Length; k++) {
                string[] hstr = lines[k].Split(' ');
                n1 = Int32.Parse(hstr[0]);
                n2 = Int32.Parse(hstr[1]);
                Graph[n1-1, n2-1] = 1;
                Graph[n2-1, n1-1] = 1;
 
            }
            for (int i = 0; i < vertex_count; i++) {
                for (int j = 0; j < edge_count; j++) {
                    Console.Write(Graph[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
 
            cnt = new int[vertex_count];
 
            for (int i = 0; i < vertex_count; i++) {
                bool[] Use = new bool[vertex_count];
                for(int j = 0; j < edge_count; j++) {
 
                    Use[j] = false;
                }
                Use[i] = true;
                DFS(Use, i, i, 0);
            }
 
            int y = 0;
            string s; 
            for (int i = 2; i < vertex_count; i++) {
                y = cnt[i]/(i*2); 
                s = "cnt[" + Convert.ToString(i) + "]: " + Convert.ToString(y);
                Console.WriteLine(s);
            }
            Console.ReadKey();
        }
        public static void DFS (bool []use, int k, int anc, int wave) 
        {
           if (Graph[k, anc] != 0) cnt[wave+1]++;
           use[k] = true;
           for(int i = 0; i < vertex_count; i++)
           {
               if (!use[i] && Graph[k,i] != 0)
               {
                   use[i] = true;
                   DFS(use, i, anc, wave + 1);
                   use[i] = false;
               }             
           }
        }
    }
}
 

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CnVzaW5nIFN5c3RlbS5UZXh0Owp1c2luZyBTeXN0ZW0uVGhyZWFkaW5nLlRhc2tzOwp1c2luZyBTeXN0ZW0uSU87CgpuYW1lc3BhY2Ug0JrQvtC7X9Cy0L5f0YbQuNC60LvQvtCyX9CyX9Cz0YDQsNGE0LVfMV8KewogICAgY2xhc3MgUHJvZ3JhbQogICAgewogICAgICAgIHB1YmxpYyBzdGF0aWMgaW50IHZlcnRleF9jb3VudDsKICAgICAgICBwdWJsaWMgc3RhdGljIGludCBlZGdlX2NvdW50OyAKICAgICAgICBwdWJsaWMgc3RhdGljIGludFssXSBHcmFwaDsKICAgICAgICBwdWJsaWMgc3RhdGljIGludCBBbW91bnQgPSAwOwogICAgICAgIHB1YmxpYyBzdGF0aWMgaW50W10gY250OwoKICAgICAgICBzdGF0aWMgdm9pZCBNYWluKHN0cmluZ1tdIGFyZ3MpCiAgICAgICAgewogICAgICAgICAgICBpbnQgbjEsIG4yOyAKICAgICAgICAgICAgc3RyaW5nW10gbGluZXMgPSBGaWxlLlJlYWRBbGxMaW5lcygiZ3JhcGgudHh0Iik7CiAgICAgICAgICAgIHN0cmluZ1tdIHN0ciA9IGxpbmVzWzBdLlNwbGl0KCcgJyk7CiAgICAgICAgICAgIHZlcnRleF9jb3VudCA9IEludDMyLlBhcnNlKHN0clswXSk7CiAgICAgICAgICAgIGVkZ2VfY291bnQgPSBJbnQzMi5QYXJzZShzdHJbMV0pOwoKICAgICAgICAgICAgR3JhcGggPSBuZXcgaW50W3ZlcnRleF9jb3VudCwgZWRnZV9jb3VudF07CgogICAgICAgICAgICBmb3IgKGludCBrID0gMTsgayA8IGxpbmVzLkxlbmd0aDsgaysrKSB7CiAgICAgICAgICAgICAgICBzdHJpbmdbXSBoc3RyID0gbGluZXNba10uU3BsaXQoJyAnKTsKICAgICAgICAgICAgICAgIG4xID0gSW50MzIuUGFyc2UoaHN0clswXSk7CiAgICAgICAgICAgICAgICBuMiA9IEludDMyLlBhcnNlKGhzdHJbMV0pOwogICAgICAgICAgICAgICAgR3JhcGhbbjEtMSwgbjItMV0gPSAxOwogICAgICAgICAgICAgICAgR3JhcGhbbjItMSwgbjEtMV0gPSAxOwoKICAgICAgICAgICAgfQogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHZlcnRleF9jb3VudDsgaSsrKSB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IGVkZ2VfY291bnQ7IGorKykgewogICAgICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGUoR3JhcGhbaSwgal0gKyAiICIpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZSgpOwoKICAgICAgICAgICAgY250ID0gbmV3IGludFt2ZXJ0ZXhfY291bnRdOwoKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCB2ZXJ0ZXhfY291bnQ7IGkrKykgewogICAgICAgICAgICAgICAgYm9vbFtdIFVzZSA9IG5ldyBib29sW3ZlcnRleF9jb3VudF07CiAgICAgICAgICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgZWRnZV9jb3VudDsgaisrKSB7CgogICAgICAgICAgICAgICAgICAgIFVzZVtqXSA9IGZhbHNlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgVXNlW2ldID0gdHJ1ZTsKICAgICAgICAgICAgICAgIERGUyhVc2UsIGksIGksIDApOwogICAgICAgICAgICB9CgogICAgICAgICAgICBpbnQgeSA9IDA7CiAgICAgICAgICAgIHN0cmluZyBzOyAKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDI7IGkgPCB2ZXJ0ZXhfY291bnQ7IGkrKykgewogICAgICAgICAgICAgICAgeSA9IGNudFtpXS8oaSoyKTsgCiAgICAgICAgICAgICAgICBzID0gImNudFsiICsgQ29udmVydC5Ub1N0cmluZyhpKSArICJdOiAiICsgQ29udmVydC5Ub1N0cmluZyh5KTsKICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHMpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIENvbnNvbGUuUmVhZEtleSgpOwogICAgICAgIH0KICAgICAgICBwdWJsaWMgc3RhdGljIHZvaWQgREZTIChib29sIFtddXNlLCBpbnQgaywgaW50IGFuYywgaW50IHdhdmUpIAogICAgICAgIHsKICAgICAgICAgICBpZiAoR3JhcGhbaywgYW5jXSAhPSAwKSBjbnRbd2F2ZSsxXSsrOwogICAgICAgICAgIHVzZVtrXSA9IHRydWU7CiAgICAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IHZlcnRleF9jb3VudDsgaSsrKQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgaWYgKCF1c2VbaV0gJiYgR3JhcGhbayxpXSAhPSAwKQogICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICB1c2VbaV0gPSB0cnVlOwogICAgICAgICAgICAgICAgICAgREZTKHVzZSwgaSwgYW5jLCB3YXZlICsgMSk7CiAgICAgICAgICAgICAgICAgICB1c2VbaV0gPSBmYWxzZTsKICAgICAgICAgICAgICAgfSAgICAgICAgICAgICAKICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cg==