//https://russianblogs.com/article/474724617/
//https://russianblogs.com/article/6212218691/
//https://codeforces.com/blog/entry/2692?locale=ru
//https://www.geeksforgeeks.org/add-and-remove-edge-in-adjacency-list-representation-of-a-graph/
//https://algorithms.tutorialhorizon.com/given-graph-remove-a-vertex-and-all-edges-connect-to-the-vertex/
//https://stackoverflow.com/questions/59045309/is-it-possible-to-also-delete-certain-edges-as-well-in-a-weighted-graph
//https://www.baeldung.com/java-graphs
//https://www.softwaretestinghelp.com/java-graph-tutorial/
//https://www.quora.com/How-do-I-efficiently-delete-an-edge-in-an-undirected-graph
//https://www.freecodecamp.org/news/graph-algorithms-and-data-structures-explained-with-java-and-c-examples/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * Container class to different classes, that makes the whole
 * set of classes one class formally.
 */
public class GraphTask {

   /**
    * Main method.
    */
   public static void main(String[] args) throws Exception {
      GraphTask a = new GraphTask();
      a.run();
   }

   /**
    * Actual main method to run examples and everything.
    */
   public void run() throws Exception {
      testSimpleGraph();
      testBiggerGraph();
      testRandomGraph();
   }


   /**
    * @throws Exception if program does not work with small graph
    */
   public void testSimpleGraph() throws Exception {
      Graph g = new Graph("G");

      Vertex a = new Vertex("A");
      Vertex b = new Vertex("B");
      Vertex c = new Vertex("C");

      g.firstVertex = a;
      g.firstVertex.nextVertex = b;
      g.firstVertex.nextVertex.nextVertex = c;

      g.info = 3;

      a.firstArc = new Arc("AB", b, new Arc("AC", c, null));
      b.firstArc = new Arc("BA", a, new Arc("BC", c, null));
      c.firstArc = new Arc("CA", a, new Arc("CB", b, null));

      g.simplify();

      if (a.firstArc.nextArc != null || b.firstArc.nextArc != null || c.firstArc.nextArc != null) {
         throw new Exception("Program is not working correctly");
      }
   }

   public void testBiggerGraph() throws Exception {
      Graph g = new Graph("G");

      Vertex a = new Vertex("A");
      Vertex b = new Vertex("B");
      Vertex c = new Vertex("C");
      Vertex d = new Vertex("D");

      g.firstVertex = a;
      g.firstVertex.nextVertex = b;
      g.firstVertex.nextVertex.nextVertex = c;
      g.firstVertex.nextVertex.nextVertex.nextVertex = d;

      g.info = 4;

      a.firstArc = new Arc("AB", b, new Arc("AC", c, null));
      b.firstArc = new Arc("BA", a, new Arc("BC", c, null));
      c.firstArc = new Arc("CA", a, new Arc("CB", b, new Arc("CD", d, null)));
      d.firstArc = new Arc("DC", c, null);

      System.out.println(g);
      g.simplify();
      System.out.println(g);

      if (a.firstArc.nextArc != null || b.firstArc.nextArc != null || c.firstArc.nextArc.nextArc != null || d.firstArc == null) {
         throw new Exception("Program is not working correctly");
      }
   }


   /**
    * visual test with random graph
    */
   public void testRandomGraph() {
      Graph g = new Graph("G");
      g.createRandomSimpleGraph(6, 9);
      System.out.println(g.createSimpleMatrix());
      System.out.println(g);
      g.simplify();
      System.out.println(g.createSimpleMatrix());
      System.out.println(g);
   }

   class Vertex {

      private String id;
      private Vertex nextVertex;
      private Arc firstArc;
      private int info = 0;

      Vertex(String s, Vertex v, Arc e) {
         id = s;
         nextVertex = v;
         firstArc = e;
      }

      Vertex(String s) {
         this(s, null, null);
      }

      @Override
      public String toString() {
         return id;
      }
   }


   /**
    * Arc represents one arrow in the graph. Two-directional edges are
    * represented by two Arc objects (for both directions).
    */
   class Arc {

      private String id;
      private Vertex target;
      private Arc nextArc;
      private int info = 0;

      Arc(String s, Vertex v, Arc a) {
         id = s;
         target = v;
         nextArc = a;
      }

      Arc(String s) {
         this(s, null, null);
      }

      @Override
      public String toString() {
         return id;
      }
   }


   class Graph {

      private String id;
      private Vertex firstVertex;
      private int info = 0;

      Graph(String s, Vertex v) {
         id = s;
         firstVertex = v;
      }

      Graph(String s) {
         this(s, null);
      }

      @Override
      public String toString() {
         String nl = System.getProperty("line.separator");
         StringBuffer sb = new StringBuffer(nl);
         sb.append(id);
         sb.append(nl);
         Vertex v = firstVertex;
         while (v != null) {
            sb.append(v.toString());
            sb.append(" -->");
            Arc a = v.firstArc;
            while (a != null) {
               sb.append(" ");
               sb.append(a.toString());
               sb.append(" (");
               sb.append(v.toString());
               sb.append("->");
               sb.append(a.target.toString());
               sb.append(")");
               a = a.nextArc;
            }
            sb.append(nl);
            v = v.nextVertex;
         }
         return sb.toString();
      }

      public Vertex createVertex(String vid) {
         Vertex res = new Vertex(vid);
         res.nextVertex = firstVertex;
         firstVertex = res;
         return res;
      }

      public Arc createArc(String aid, Vertex from, Vertex to) {
         Arc res = new Arc(aid);
         res.nextArc = from.firstArc;
         from.firstArc = res;
         res.target = to;
         return res;
      }

      /**
       * Create a connected undirected random tree with n vertices.
       * Each new vertex is connected to some random existing vertex.
       *
       * @param n number of vertices added to this graph
       */
      public void createRandomTree(int n) {
         if (n <= 0)
            return;
         Vertex[] varray = new Vertex[n];
         for (int i = 0; i < n; i++) {
            varray[i] = createVertex("v" + String.valueOf(n - i));
            if (i > 0) {
               int vnr = (int) (Math.random() * i);
               createArc("a" + varray[vnr].toString() + "_"
                       + varray[i].toString(), varray[vnr], varray[i]);
               createArc("a" + varray[i].toString() + "_"
                       + varray[vnr].toString(), varray[i], varray[vnr]);
            }
         }
      }

      /**
       * Create an adjacency matrix of this graph.
       * Side effect: corrupts info fields in the graph
       *
       * @return adjacency matrix
       */
      public int[][] createAdjMatrix() {
         info = 0;
         Vertex v = firstVertex;
         while (v != null) {
            v.info = info++;
            v = v.nextVertex;
         }
         int[][] res = new int[info][info];
         v = firstVertex;
         while (v != null) {
            int i = v.info;
            Arc a = v.firstArc;
            while (a != null) {
               int j = a.target.info;
               res[i][j]++;
               a = a.nextArc;
            }
            v = v.nextVertex;
         }
         return res;
      }

      /**
       * Create a connected simple (undirected, no loops, no multiple
       * arcs) random graph with n vertices and m edges.
       *
       * @param n number of vertices
       * @param m number of edges
       */
      public void createRandomSimpleGraph(int n, int m) {
         if (n <= 0)
            return;
         if (n > 2500)
            throw new IllegalArgumentException("Too many vertices: " + n);
         if (m < n - 1 || m > n * (n - 1) / 2)
            throw new IllegalArgumentException
                    ("Impossible number of edges: " + m);
         firstVertex = null;
         createRandomTree(n);       // n-1 edges created here
         Vertex[] vert = new Vertex[n];
         Vertex v = firstVertex;
         int c = 0;
         while (v != null) {
            vert[c++] = v;
            v = v.nextVertex;
         }
         int[][] connected = createAdjMatrix();
         int edgeCount = m - n + 1;  // remaining edges
         while (edgeCount > 0) {
            int i = (int) (Math.random() * n);  // random source
            int j = (int) (Math.random() * n);  // random target
            if (i == j)
               continue;  // no loops
            if (connected[i][j] != 0 || connected[j][i] != 0)
               continue;  // no multiple edges
            Vertex vi = vert[i];
            Vertex vj = vert[j];
            createArc("a" + vi.toString() + "_" + vj.toString(), vi, vj);
            connected[i][j] = 1;
            createArc("a" + vj.toString() + "_" + vi.toString(), vj, vi);
            connected[j][i] = 1;
            edgeCount--;  // a new edge happily created
         }
      }


      /**
       * @return matrix containing directions
       */
      public String createSimpleMatrix() {
         String nl = System.getProperty("line.separator");
         StringBuffer sb = new StringBuffer(nl);
         sb.append("   ");
         int w = 0;
         Vertex[] vv = getVertexArray();
         Arrays.stream(vv).forEach(a -> {
            sb.append(a.toString());
            sb.append(" ");
         });
         sb.append(nl);
         Vertex v = firstVertex;
         while (v != null) {
            sb.append(v.toString());
            int i = 0;
            while (i != info) {
               Arc a = v.firstArc;
               sb.append("  ");
               while (a != null) {
                  if (a.target == vv[i]) {
                     sb.append(1);
                     break;
                  }
                  a = a.nextArc;
               }
               if (a == null) {
                  sb.append(0);
               }
               i += 1;
            }
            sb.append(nl);
            v = v.nextVertex;
         }
         return sb.toString();
      }


      /**
       * @return array containing all vertexs in this graph
       */
      public Vertex[] getVertexArray() {
         Vertex vert = firstVertex;
         Vertex[] vertArray = new Vertex[info];
         int index = 0;
         while (vert != null) {
            vertArray[index] = vert;
            index++;
            vert = vert.nextVertex;
         }
         return vertArray;
      }


      /**
       * deletes all arcs not mentioned in findMinimumArcs() from this graph.
       */
      public void simplify() {
         List<Arc> arcList = findTheMinimumArcs();
         Vertex vert = firstVertex;
         Arc a;
         Arc b;
         while (vert != null) {
            a = vert.firstArc;
            b = a;
            while (a != null) {
               if (arcList.contains(a)) {
                  b = a;
               } else {
                  if (vert.firstArc == a) {
                     vert.firstArc = a.nextArc;
                  }
               }
               b.nextArc = a.nextArc;
               a = a.nextArc;
            }
            vert = vert.nextVertex;
         }
      }


      /**
       * finds the ringway of arcs and vertexs in the graph
       *
       * @return list of arcs that are essential for the ringway
       */
      public List<Arc> findTheMinimumArcs() {
         List<Arc> arcs = new ArrayList<>();
         List<Vertex> vertexList = new ArrayList<>();
         HashSet<Vertex> vertexs = new HashSet<>();

         vertexList.add(firstVertex);
         vertexs.add(firstVertex);

         Arc first = firstVertex.firstArc;
         while (vertexs.size() != info || vertexList.get(0) != first.target) {

            // check if there are already a lot of arcs
            if (arcs.size() > info) {

               // check whether algorithm is looping between two vertexs
               if (first == arcs.get(arcs.size() - 2) && first == arcs.get(arcs.size() - 4)) {
                  if (first.nextArc != null) {
                     first = first.nextArc;
                  } else {
                     vertexList = vertexList.subList(0, vertexList.size() - 1);
                     while (arcs.get(arcs.size() - 1).nextArc == null) {
                        vertexList = vertexList.subList(0, vertexList.size() - 1);
                        arcs = arcs.subList(0, arcs.size() - 1);
                     }
                     first = arcs.get(arcs.size() - 1).nextArc;
                     arcs = arcs.subList(0, arcs.size() - 1);
                  }
               }

            } else if (!vertexs.contains(first.target) || !vertexList.contains(first.target)) {

               // if not used vertex found go there
               vertexList.add(first.target);
               vertexs.add(first.target);
               arcs.add(first);
               first = first.target.firstArc;
            } else if (first.nextArc != null) {

               // if this vertex is already used, then next arc
               first = first.nextArc;
            } else if (first == vertexList.get(vertexList.size() - 1).firstArc) {

               // if this is the only one arc going out of this vertex then use it
               vertexList.add(first.target);
               vertexs.add(first.target);
               arcs.add(first);
               first = first.target.firstArc;
            } else if (vertexs.size() == info && vertexList.containsAll(vertexs)) {

               // if we have already been everywhere and now have to find the start point
               vertexList.add(first.target);
               arcs.add(first);
               if (vertexList.get(0) == first.target.firstArc.target) {
                  vertexList.add(first.target.firstArc.target);
                  arcs.add(first.target.firstArc);
                  break;
               }
               first = first.target.firstArc;
            } else {

               // going some steps back and switching the current arc to next if possible
               vertexList = vertexList.subList(0, vertexList.size() - 1);
               while (arcs.get(arcs.size() - 1).nextArc == null) {
                  vertexList = vertexList.subList(0, vertexList.size() - 1);
                  arcs = arcs.subList(0, arcs.size() - 1);
               }
               first = arcs.get(arcs.size() - 1).nextArc;
               arcs = arcs.subList(0, arcs.size() - 1);
            }

            // if all the vertexs are used and now we can finish the loop
            if (vertexList.get(0) == first.target && vertexList.containsAll(vertexs) && vertexs.size() == info) {
               vertexList.add(first.target);
               arcs.add(first);
               break;
            }
         }
         return arcs;
      }
   }
}