using System;
using System.Collections.Generic;

namespace Lista9v3
{
    class Program
    {
        static int[,] graf;
        static int[,] zbior;
        static int wielkoscZbioru;
        static Random losowa = new Random();
        static List<List<int>> key = new List<List<int>>();

        static void Main(string[] args)
        {
            int w, p;
            Console.Write("Podaj ile wierzcholkow ma miec graf >> ");
            w = Convert.ToInt32(Console.ReadLine());
            Console.Write("Podaj prawdopodobienstwo ilosci krawedzi wychodzacych z wierzcholka >> ");
            p = Convert.ToInt32(Console.ReadLine());
            p = losowa.Next(1, p);

            zbior = new int[w * w, 2];
            wielkoscZbioru = w * w;
            createZbior(w, p);
            clearZbior();

            graf = new int[w, 2];
            createGraf(w);

            lista(w);
            BFS(w);
        }

        static void BFS(int w)
        {
            int start, szukany, licznik = 0;

            Console.WriteLine("");
            Console.Write("Podaj wierzcholek startowy >> ");
            start = Convert.ToInt32(Console.ReadLine());
            Console.Write("Podaj wierzcholek szukany >> ");
            szukany = Convert.ToInt32(Console.ReadLine());

            bool[] visit = new bool[w+1];
            int[] licz = new int[w+1];
            Queue<int> kolejka = new Queue<int>();

            for(int i = 0; i < w; i++)
            {
                visit[i] = false;
                licz[i] = -1;
            }

            licznik++;
            kolejka.Enqueue(start);
            visit[start] = true;
            licz[start] = licznik;
            bool f = false;
            List<int> next;

                while (kolejka.Count > 0 && !f)
                {
                    start = kolejka.Dequeue();
                    visit[start] = true;
                Console.WriteLine("Sciagam liczbe z kolejki " + start + " sprawdzam czy jest równa szukanej = " + szukany);
                    if (start == szukany)
                    {
                    Console.WriteLine("Znalazlem");
                        licznik++;
                        licz[szukany] = licznik;
                    f = true;
                    }
                    else
                    {
                        licznik++;
                        next = key[start];
                    Console.Write("Wczytuje do kolejnki nastepnikow: ");
                        for (int i = 0; i < next.Count; i++)
                        {
                            if (!visit[next[i]])
                             {
                             kolejka.Enqueue(next[i]);
                                licz[next[i]] = licznik;
                                Console.Write(next[i] + " ");
                             }
                        }
                    Console.WriteLine("");
                    }
                }


                for (int i = 0; i < w; i++)
                {
                    if (visit[i])
                    {

                    }
                }
        }

        static void lista(int w)
        {
            for(int i = 0; i <= w; i++)
            {
                List<int> next = new List<int>();

                for(int j = 0; j < w; j++)
                {
                    if(graf[j, 0] == i)
                    {
                        next.Add(graf[j, 1]);
                    }
                }
                key.Add(next);
            }
            listaShow(w);
        }

        static void listaShow(int w)
        {
            List<int> next;

            for(int i = 0; i < w; i++)
            {
                next = key[i];
                if (next.Count > 0)
                {
                    Console.WriteLine("");
                    Console.Write(i + " ");

                    for (int j = 0; j < next.Count; j++)
                    {
                        Console.Write(next[j] + " ");
                    }
                }
            }
        }

        static void clearZbior()
        {
            int v1, v2;

            for (int j = 0; j < wielkoscZbioru; j++)
            {
                v1 = zbior[j, 0];
                v2 = zbior[j, 1];

                if (v1 == v2)
                {
                    zbior[j, 0] = zbior[wielkoscZbioru - 1, 0];
                    zbior[j, 1] = zbior[wielkoscZbioru - 1, 1];
                    wielkoscZbioru--;
                }
            }
        }

        static void clearZbior(int l)
        {
            zbior[l, 0] = zbior[wielkoscZbioru - 1, 0];
            zbior[l, 1] = zbior[wielkoscZbioru - 1, 1];

            wielkoscZbioru--;
        }

        static void createZbior(int w, int p)
        {
            int liczba = 1, licznik = 0;

            while (liczba <= w)
            {
                for (int i = licznik; i < w + licznik; i++)
                {
                    zbior[i, 0] = liczba;
                }

                for (int j = 1; j <= w; j++)
                {
                    zbior[(j - 1) + licznik, 1] = j;
                }

                liczba++;
                licznik = licznik + w;
            }
            wielkoscZbioru--;
        }


        static void createGraf(int w)
        {
            int l;

            for (int i = 0; i < w; i=i+2)
            {
                l = losowa.Next(0, wielkoscZbioru - 1);

                graf[i, 0] = zbior[l, 0];
                graf[i, 1] = zbior[l, 1];
                graf[i + 1, 0] = zbior[l, 1];
                graf[i + 1, 1] = zbior[l, 0];

                for(int j = 0; j < wielkoscZbioru; j++)
                {
                    if(zbior[j, 0] == graf[i + 1, 0] && zbior[j, 1] == graf[i + 1, 1])
                    {
                        clearZbior(j);
                        break;
                    }
                }

                clearZbior(l);
            }

            showgraf(w);
        }

        static void showgraf(int w)
        {
            for (int i = 0; i < w; i++)
            {
                Console.WriteLine(graf[i, 0] + " " + graf[i, 1]);
            }
        }
    }
}