using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Pruf
{
    internal class Pr
    {
        List<List<int>> graph;
        List<int> codePreufer;
        public Pr(List<List<int>> graph)
        {
            this.graph = graph;
            codePreufer = new List<int>();
        }

        bool SearchLeaf(int leaf)
        {
            int counter=0;

            for (int i = 0; i < graph.Count; i++)
            {
                for (int j = 0; j < graph[i].Count; j++)
                {
                    if (leaf == graph[i][j])
                        counter++;
                }
            }
            if (counter > 1)
                return false;
            else 
                return true;
        }

        public void RealizationAlg()
        {
            while (true)
            {
                int minLeaf = int.MaxValue;
                int indexRow = int.MaxValue;
                int indexCol = int.MaxValue;
                if (graph.Count == 1)
                    break;

                List<List<int>> leaves = new List<List<int>>();
                for (int i = 0; i < graph.Count; i++)
                {
                    for (int j = 0; j < graph[i].Count; j++)
                    {
                        List<int> leafAndIndexes = new List<int>();
                        if (SearchLeaf(graph[i][j]))
                        {                           
                            leafAndIndexes.Add(graph[i][j]);
                            leafAndIndexes.Add(i);
                            leafAndIndexes.Add(j);
                            leaves.Add(leafAndIndexes);
                        }
                    }
                }

                for (int i = 0; i < leaves.Count; i++)
                {
                    if (minLeaf > leaves[i][0])
                    {
                        minLeaf = leaves[i][0];
                        indexRow = leaves[i][1];
                        indexCol = leaves[i][2];
                    }
                }

                if (indexCol == 0)
                {
                    codePreufer.Add(graph[indexRow][1]);
                    graph.RemoveAt(indexRow);
                }
                else
                {
                    codePreufer.Add(graph[indexRow][0]);
                    graph.RemoveAt(indexRow);
                }
            }
        }
        public override string ToString() => string.Join(" ", codePreufer);
        
    }
}