class Program
 {
   static void Main(string[] args)
   {
     int w = 0;
     
     int m = 0, p = 0, n = 0;
     int[,] C = null;
     
     do
     {
       Console.WriteLine("1 - Wpisz graf ręcznie w konsoli");
       Console.WriteLine("2 - Wczytaj plik z grafem");
       Console.WriteLine("3 - Zakończ działanie programu");
       Console.Write("Wybór opcji: ");
       int.TryParse(Console.ReadLine(),out w);
       
       bool f;
       Console.WriteLine();
       switch (w)
       {
         case 1:
         f=WczytajDane(ref m, ref p, ref n, ref C);
         if(f)
         {
           AlgorytmEdmondsaKarpa(m, p, n, C);
         }
         else
         {
           Console.WriteLine("Nie udało się poprawnie wpisać danych.");
         }
         break;
         case 2:
         f = WczytajPlik(ref m, ref p, ref n, ref C);
         if(f)
         {
           AlgorytmEdmondsaKarpa(m, p, n, C);
         }
         else
         {
           Console.WriteLine("Nie udało się odczytać danych.");
         }
         break;
       }
       Console.WriteLine();
     } while (w!=3); 
   }
   
   public static void AlgorytmEdmondsaKarpa(int m, int p, int n, int[,] C)
   {
     int[,] F = new int[n + 2, n + 2];
     int fmax = 0;
     Queue<int> Q = new Queue<int>();
     
     int[] P = new int[n + 2];
     int[] CFP = new int[n + 2];
     while (true)
     {
       for (int i = 0; i <= n + 1; i++) P[i] = -1;
       
       P[n] = -2;
       CFP[n] = 9999999;
       
       Q.Clear();
       Q.Enqueue(n);
       
       bool esc = false;
       
       while (Q.Count != 0)
       {
         int v = Q.Dequeue();
         
         
         for (int u = 0; u <= n + 1; u++)
         {
           int cp = C[v, u] - F[v, u];
           if ((cp != 0) && (P[u] == -1))
           {
             P[u] = v;
             if (CFP[v] > cp) CFP[u] = cp; else CFP[u] = CFP[v];
             if (u == n + 1)
             {
               fmax += CFP[n + 1];
               int i = u;
               while (i != n)
               {
                 v = P[i];
                 F[v, i] += CFP[n + 1];
                 F[i, v] -= CFP[n + 1];
                 i = v;
               }
               esc = true; break;
             }
             Q.Enqueue(u);
           }
         }
         if (esc) break;
       }
       if (!esc) break;
     }
     
     Console.WriteLine();
     Console.WriteLine("Wynik:");
     
     if (fmax > 0)
       for (int v = m; v < n; v++)
       {
         bool znaleziono = false;
         for (int u = 0; u < n; u++)
           if ((C[v, u] == 1) && (F[v, u] == 1))
           {
             int nrM = u + 1;
             int nrP = v - m + 1;
             Console.WriteLine("Pracownik nr {0} - maszyna {1}", nrP, nrM);
             znaleziono = true;
             break;
           }
         if (znaleziono == false)
         {
           int nrP = v - m + 1;
           Console.WriteLine("Pracownik nr {0} - brak maszyny", nrP);
         }
       }
     
     Console.WriteLine();
     Console.Write("Kliknij dowolny przycisk aby kontynuować...");
     Console.ReadKey();
     Console.WriteLine();
   }
   
   public static bool WczytajDane(ref int m, ref int p, ref int n, ref int[,] C)
   {
     Console.Write("Podaj ilość maszyn: ");
     if (!int.TryParse(Console.ReadLine(), out m)) return false;
     Console.Write("Podaj ilość pracowników: ");
     if (!int.TryParse(Console.ReadLine(), out p)) return false;
     n = p + m;
     C = new int[n + 2, n + 2];
     
     for (int i = 0; i < m; i++)
     {
       C[i, n + 1] = 1;
     }
     for (int i = 0; i < p; i++)
     {
       Console.WriteLine("Podaj numery maszyn, które może obsługiwać pracownik nr {0} (Oddzielone spacją, zatwierdź enterem)", i + 1);
       string[] wejscie = Console.ReadLine().Split(' ');
       int tmp = 0;
       for (int j = 0; j < wejscie.Length; j++)
       {
         if (wejscie[j] == "" || int.Parse(wejscie[j]) > m || int.Parse(wejscie[j]) < 0)
           continue;
         if (!int.TryParse(wejscie[j], out tmp)) return false;
         C[m + i, tmp - 1] = 1;
       }
       C[m + i, n] = 1;
     }
     for (int i = 0; i < p; i++)
     {
       C[n, i + m] = 1;
     }
     
     return true;
   }
   
   public static bool WczytajPlik(ref int m,ref int p,ref int n, ref int[,]C )
   {
     string nazwa="";
     Console.Write("Wpisz nazwę pliku: ");
     nazwa = Console.ReadLine();
     StreamReader sr=null;
     
     try
     {
       sr = new StreamReader(nazwa + ".txt");
     }
     catch (Exception)
     {
       Console.WriteLine("Nie znaleziono pliku.");
       return false;
     }
     
     
     if (sr != null)
     {
       if (!int.TryParse(sr.ReadLine(), out m)) return false;
       if (!int.TryParse(sr.ReadLine(), out p)) return false;
       n = p + m;
       C = new int[n + 2, n + 2];
       
       for (int i = 0; i < m; i++)
       {
         C[i, n + 1] = 1;
       }
       for (int i = 0; i < p; i++)
       {
         string[] wejscie = sr.ReadLine().Split(' ');
         int tmp = 0;
         for (int j = 0; j < wejscie.Length; j++)
         {
           if (wejscie[j] == "" || int.Parse(wejscie[j]) > m || int.Parse(wejscie[j]) < 0)
             continue;
           if (!int.TryParse(wejscie[j], out tmp)) return false;
           C[m + i, tmp - 1] = 1;
         }
         C[m + i, n] = 1;
       }
       for (int i = 0; i < p; i++)
       {
         C[n, i + m] = 1;
       }
     }
     return true;
   }
   
   public static void WyswietlTablice(int[,] G)
   {
     for (int i = 0; i < G.GetLength(0); i++)
     {
       for (int j = 0; j < G.GetLength(1); j++)
       {
         Console.Write(G[i, j] + " ");
       }
       Console.WriteLine();
     }
     Console.WriteLine();
   }
   public static void WyswietlTablice(int[] G)
   {
     for (int i = 0; i < G.GetLength(0); i++)
     {
       Console.Write(G[i] + " ");
     }
     Console.WriteLine();
     Console.WriteLine();
   }
 }