using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program{

​

    private static List<List<int>> FindPermutations(params int[] nums){

        List<List<int>> result = new List<List<int>>();

        Backtrack(result, new List<int>(), new bool[nums.Length], nums);

        return result;

    }

​

    private static void Backtrack(List<List<int>> dList, List<int> list, bool[] used, int[] nums){

        if(list.Count == nums.Length) {

            dList.Add(new List<int>(list));

            return;

        }

        for(int i = 0; i < nums.Length; i++) {

            if(used[i]) continue;

            used[i] = true;

            list.Add(nums[i]);

            Backtrack(dList, list, used, nums);

            list.RemoveAt(list.Count - 1);

            used[i] = false;

        }

    }

​

    private static int FindOverlap(List<int> superPerm, List<int> perm){

        for(int i = 1; i < superPerm.Count; i++) if(superPerm.Skip(superPerm.Count - i).SequenceEqual(perm.Take(i))) return i;

        return 0;

    }

​

    private static List<int> GetMinimalSuperPermutation(List<List<int>> permutations){

        List<int> result = new List<int>(permutations[0]);

        HashSet<int> used = new HashSet<int>{0};

        while(used.Count < permutations.Count){

            int maxOverlap = -1;

            List<int> p1 = null;

            int index = -1;

            for(int i = 0; i < permutations.Count; i++){

                if(used.Contains(i)) continue;

                List<int> p2 = permutations[i];

                int overlap = FindOverlap(result, p2);

                if(overlap > maxOverlap){

                    maxOverlap = overlap;

                    p1 = p2;

                    index = i;

                }

            }

            if(p1 != null){

                result.AddRange(p1.Skip(maxOverlap));

                used.Add(index);

            }

        }

        return result;

    }

​

    public static List<int> ChainPermutations(List<List<int>> permutations){

        List<int> result = new List<int>(permutations[0]);

        HashSet<int> used = new HashSet<int>();

        used.Add(0);

        while(used.Count < permutations.Count){

            var p1 = permutations.FirstOrDefault(p => !used.Contains(permutations.IndexOf(p)) && p[0] == result.Last());

            if(p1 == null) break;

            result.AddRange(p1.Skip(1));

            used.Add(permutations.IndexOf(p1));

        }

        return result;

    }

​

    public static void Main(){

        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7};

        List<List<int>> permutations = FindPermutations(nums);

//      foreach(List<int> list in permutations) Console.WriteLine($"{string.Join(",", list)}");

        Console.WriteLine(permutations.Count * 6);

        List<int> chainedPermutations = GetMinimalSuperPermutation(permutations);

        Console.WriteLine($"{string.Join("", chainedPermutations)}");

        Console.WriteLine(chainedPermutations.Count);

    }

​

}