#include <bits/stdc++.h>
using namespace std;
const int maxn = 300;
pair<int, int> dp[maxn];  // lis
pair<int, int> dp2[maxn]; // lds
bool removed[maxn];
int a[maxn];
bool used[maxn];
unordered_map<int, vector<int>> g;
unordered_map<int, int> m;
int timer = 1;
void dfs(int u, int par)
{
      a[timer] = u;
      timer++;
      for (auto x : g[u])
      {
            if (x != par)
                  dfs(x, u);
      }
}
std::vector<int> encode(int N, std::vector<std::pair<int, int>> v)
{
      for (auto x : v)
      {
            g[x.first].push_back(x.second);
            g[x.second].push_back(x.first);
      }
      dfs(1, -1);
      int maxi = 0;
      int ind = -1;
      int maxi2 = 0;
      int ind2 = -1;
      for (int i = 1; i <= N; i++)
      {
            for (int j = 0; j < i; j++)
            {
                  if (a[i] > a[j])
                  {
                        if (dp[i].first < dp[j].first + 1)
                        {
                              dp[i].first = dp[j].first + 1;
                              dp[i].second = j;
                        }
                  }
                  else
                  {
                        if (a[i] < a[j] || j == 0)
                        {
                              if (dp2[i].first < dp2[j].first + 1)
                              {
                                    dp2[i].first = dp2[j].first + 1;
                                    dp2[i].second = j;
                              }
                        }
                  }
            }
            if (maxi < dp[i].first)
            {
                  maxi = dp[i].first;
                  ind = i;
            }
            if (maxi2 < dp2[i].first)
            {
                  maxi2 = dp2[i].first;
                  ind2 = i;
            }
      }

      vector<int> ans;
      if (maxi >= 16)
      {
            int br = 16;
            int st = ind;
            while (br > 0)
            {
                  ans.push_back(a[st]);

                  br--;
                  st = dp[st].second;
            }
      }
      else
      {
            int br = 17;
            int st = ind2;
            while (br > 0)
            {

                  ans.push_back(a[st]);

                  br--;
                  st = dp2[st].second;
            }
      }

      return ans;
}
std::vector<std::pair<int, int>> decode(int N, std::vector<std::pair<int,
                                                                     int>>
                                                   v)
{
      bool dali = false;
      timer = 1;
      int br = 0;
      for (auto x : v)
      {
            if (x.first == 1 || x.second == 1)
                  dali = true;
            g[x.first].push_back(x.second);
            g[x.second].push_back(x.first);
      }
      if (!dali)
            dfs(-1, INT_MAX);
      else
            dfs(1, INT_MAX);
      for (int i = 1; i <= N; i++)
      {
            if (a[i] < 0)
            {
                  br++;
            }
            else
            {
                  removed[a[i]] = true;
            }
      }
      vector<int> left;
      for (int i = 1; i <= 256; i++)
      {
            if (!removed[i])
            {
                  left.push_back(i);
            }
      }

      if (br == 17)
      {
            reverse(left.begin(), left.end());
      }
      int ind = 0;
      for (int i = 1; i <= N; i++)
      {
            if (a[i] < 0)
            {
                  m[a[i]] = left[ind];
                  ind++;
            }
            else
            {
                  m[a[i]] = a[i];
            }
      }
      vector<pair<int, int>> ans;
      for (auto x : v)
      {
            ans.push_back({m[x.first], m[x.second]});
      }
      return ans;
}
