// The program inputs N pieces of domino, each piece contains pair of integer numbers in range 0..K-1.

// The program should build and output the loop chain of given dominoes or the phrase “no loop”

// if it is impossible to build such loop.

using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    // Solution idea: consider inoriented graph where each vertex is a number that

    // is written on at least one piece of domino and each edge corresponds to one

    // piece of domino.

    //

    // Then finding the domino loop is equivalent to finding Euler's way in this graph.

    // Data representation is simpler for oriented graph, so we'll

    // split each "inoriented" domino into two oriented counterparts.

    // The data structure still remains more complicated than in case of inoriented graph,

    // since we have to mark used edges in pairs and be able to skip unused edges

    // efficiently.

    // One piece of domino.

    class Piece

    {

        public readonly int From, To;

        public Piece(int f, int t)

        {

            From = f;

            To = t;

        }

        public Piece Mirror()

        {

            return new Piece(To, From);

        }

    }

    // Vertex in a graph with chip edge removal.

    class Vertex

    {

        public int count;

        public int[] edges;

        public Vertex(int capacity)

        {

            count = 0;

            edges = new int[capacity];

        }

        public int Add(int piece)

        {

            int pos = count;

            edges[pos] = piece;

            count++;

            return pos;

        }

        public void RemoveAt(int pos)

        {

            count--;

            if(pos < count)

            {

                // To achive O(1) complexity, we'll

                // move the last element to the hole,

                // since we don't care about the edge order here.

                edges[pos] = edges[count];

            }

        }

    }

    class DominosKeeper

    {

        // We'll keep 2 "one-way" piece of of domino for each original piece.

        // "one-way" pairs go together at indexes 0,1 then 2,3 etc

        private List<Piece> m_dominos;

        // Connectivity list. Each edge keeps the index of piece in m_domino

        private Vertex[] m_edges;

        // for each piece n in m_dominos, we'll keep correspondent edge index

        // in m_edges[m_dominos[n].from]

        private int[] m_edgeIndexOfPiece;

        public void Init(Piece[] dominos, int K)

        {

            // Allocate 2 "one-way" domino pieces per each input

            int N = 2 * dominos.Length;

            m_dominos = new List<Piece>(N);

            foreach(Piece d in dominos)

            {

                m_dominos.Add(d);

                m_dominos.Add(d.Mirror());

            }

            // Count required capacities

            int [] capacity = new int[K];

            foreach(Piece piece in m_dominos)

            {

                capacity[piece.From]++;

            }

            // Allocate edge representation

            m_edges = new Vertex[N];

            for (int v = 0; v < K; v++)

            {

                m_edges[v] = new Vertex(capacity[v]);

            }

            // Fill edge representation

            m_edgeIndexOfPiece = new int[N];

            for (int nPiece = 0; nPiece < N; nPiece++)

            {

                Piece d = m_dominos[nPiece];

                int vertex = d.From;

                int pos = m_edges[vertex].Add(nPiece);

                UpdatePosition(vertex, pos);

            }

        }

        // make sure we have right value in m_pos for given edge

        public void UpdatePosition(int vertex, int edgeIndex)

        {

            int nPiece = m_edges[vertex].edges[edgeIndex];

            m_edgeIndexOfPiece[nPiece] = edgeIndex;

        }

        // O(1) removal of edge

        // Cannot do that fast with List.RemoveAt

        public void RemoveEdgeAt(int nPiece)

        {

            int vertex = m_dominos[nPiece].From;

            int pos = m_edgeIndexOfPiece[nPiece];

            m_edges[vertex].RemoveAt(pos);

            if (pos < m_edges[vertex].count)

            {

                UpdatePosition(vertex, pos);

            }

        }

        // Remove both halves of real domino piece

        public void RemovePiece(int nPiece)

        {

            RemoveEdgeAt(nPiece);

            // we need adjacent odd for even and vice versa

            // this will do the trick

            RemoveEdgeAt(nPiece ^ 1);

        }

        public IList<Piece> FindLoop()

        {

            if (0 == m_dominos.Count)

                return m_dominos;  // assume that empty set is a loop

            int N = m_dominos.Count / 2;    // number of actual pieces

            Queue<int> path = new Queue<int>(N);

            // Invariant:

            // Path contains a chain of domino pieces starting with

            // vertexFrom and ending with vertex.

            // Graph contain remaining pieces (2 edges per original piece).

            int vertex = m_dominos[0].From;  // just pick non-isolated vertex

            int vertexFrom = vertex;

            int nShifts = 1;

            while(path.Count < N && nShifts > 0)

            {

                if(m_edges[vertex].count > 0)

                {   // extend the path

                    int nPiece = m_edges[vertex].edges[0];

                    path.Enqueue(nPiece);

                    RemovePiece(nPiece);

                    vertex = m_dominos[nPiece].To;

                    nShifts = path.Count;

                }

                else if(vertexFrom == vertex)

                {   // rotate the path

                    int nPiece = path.Dequeue();

                    path.Enqueue(nPiece);

                    vertex = m_dominos[nPiece].To;

                    vertexFrom = vertex;

                    nShifts--;

                }

                else

                {   // dead end - no loop found

                    return null;

                }

            }

            // we cannot add more elements to loop

            if (path.Count < N)

                return null;    // cannot add all

            if (vertexFrom != vertex)

                return null;    // we have full chain, but not a loop

            // convert to array of pieces

            return path.Select(nPiece => m_dominos[nPiece]).ToList();

        }

    }

​

    public static void Main()

    {

        Test("simple", new []{ 0,0, 0,1, 0,1, 1,1}, 2);

        Test("complex", new []{ 0,0, 0,1, 0,1, 1,1, 0,2, 2,3, 3,0}, 4);

        Test("Kenigsberg", new []{ 0,1, 0,1, 0,2, 0,2, 0,3, 1,3, 2,3}, 4);

    }

​

​

    static void Test(string title, int [] fromto, int K)

    {

        int N = fromto.Length / 2;

        Piece [] pieces = new Piece[N];

        for(int i=0;i<N;i++)

        {

            pieces[i] = new Piece(fromto[2*i], fromto[2*i+1]);

        }

        DominosKeeper keeper = new DominosKeeper();

        keeper.Init(pieces, K);

        IList<Piece> r = keeper.FindLoop();

        if(null == r)

        {

            Console.WriteLine("{0}: No loop found", title);

            return;

        }

        Console.Write("{0}:", title);

        foreach(Piece piece in r)

        {

            Console.Write(" ({0},{1})", piece.From, piece.To);

        }

        Console.WriteLine();

    }

}