#!/bin/bash

i=1

# You can change the version of C++ or add the compiler flags you wish 
g++ -std=c++17 gen.cpp -o generator
g++ -std=c++17 solution.cpp -o original
g++ -std=c++17 brute.cpp -o brute

max_tests=10 # change it accordingly
diff_found=0

# to color the output text in different colours
green=$(tput setaf 71);
red=$(tput setaf 1);
blue=$(tput setaf 32);
orange=$(tput setaf 178);
bold=$(tput bold);
reset=$(tput sgr0);

while [ $i -le $max_tests ]
do
	# Generate test_case and save it in input1.txt
	./generator > input1.txt

	# run original solution, take input from above generated test case i.e. from input1.txt
	# and save it in original_output.txt
	./original < input1.txt > original_output.txt

	# run brute force solution, take input from above generated test case i.e. from input1.txt
	# and save it in brute_output.txt
	./brute < input1.txt > brute_output.txt

	# check if files original_output and brute_output
	# differs(we are ignoring spaces and then comparing files)
        if diff --tabsize=1 -F --label --side-by-side --ignore-space-change original_output.txt brute_output.txt > 
        dont_show_on_terminal.txt; then
	        echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${green}Accepted$$${reset}"
	else
		echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${red}Wrong Answer$$${reset}"
		diff_found=1
		break
	fi
	i=$((i+1))
done

if [ $diff_found -eq 1 ]
then
	echo "$$${blue}Input: $$${reset}"
	cat input1.txt
	echo ""

	echo "$$${blue}Output: $$${reset}"
	cat original_output.txt
	echo ""
	echo ""

	echo "$$${blue}Expected: $$${reset}"
	cat brute_output.txt
	echo ""
fi

rm input1.txt
rm generator
rm original
rm brute
rm original_output.txt
rm brute_output.txt
rm dont_show_on_terminal.txt

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define accuracy chrono::steady_clock::now().time_since_epoch().count()
#define rep(i,a,n) for (int i = a; i <= n; ++i)

const int N = 1e6 + 4;

int32_t permutation[N];

mt19937 rng(accuracy);

int rand(int l, int r){
  uniform_int_distribution<int> ludo(l, r); return ludo(rng);
}

const int inf = 1LL << 31;

using pii = pair<int,int>;

namespace generator {
  string gen_string(int len = 0, bool upperCase = false, int l = 1, int r = 26) {
    assert(len >= 0 && len <= 5e6);
    string str(len, (upperCase ? 'A' : 'a'));
    for (char &ch: str) {
      ch += rand(l, r) - 1;
    }
    return str;
  }
  vector<int> gen_array(int len = 0, int minRange = 0, int maxRange = inf){
   assert(len >= 0 and len <= 5e6);
    vector<int> a(len);
    for (int &x: a) x = rand(minRange, maxRange);
    return a;
  }
  vector<pair<int, int>> gen_tree(int n = 0){
    assert(n >= 0);
    vector<pii> res(n ? n - 1 : 0);
    // if you like to have bamboo like tree or star like tree uncomment below 8 lines
    /*if (rng() % 5 == 0) { // bamboo like tree
      for (int i = 1; i < n; ++i) res[i-1] = {i, i + 1};
      return res;
    }
    if (rng() % 7 == 0) { // star tree
      for (int i = 2; i <= n; ++i) res[i-2] = {1, i};
      return res;
    }*/
    iota(permutation, permutation + 1 + n, 0);
    shuffle(permutation + 1, permutation + 1 + n, rng);
    for(int i = 2; i <= n; ++i){
      int u = i, v = rand(1 , i-1);
      u = permutation[u], v = permutation[v];
      res[i-2] = minmax(u, v); // u < v, just for convenience while debugging
    }
    shuffle(res.begin() , res.end() , rng);
    return res;
  }
  vector<pair<int, int>> simple_graph(int n = 0, int m = 0) {
    assert(n > 0 && m >= n);
    int max_edges = n * (n - 1) / 2;
    assert(m <= max_edges);
    vector<pii> res = gen_tree(n);
    set<pii> edge(res.begin(), res.end());
    for (int i = n; i <= m; ++i) {
      while (true) {
        int u = rand(1, n), v = rand(1, n);
        if (u == v) continue;
        auto it = edge.insert(minmax(u, v));
        if (it.second) break;
      }
    }
    res.assign(edge.begin(), edge.end());
    return res;
  }
}

using namespace generator;

template<typename T = int>
ostream& operator<< (ostream &other, const vector<T> &v) {
    for (const T &x: v) other << x << ' ';
    other << '\n';
    return other;
}

ostream& operator<< (ostream &other, const vector<pair<int,int>> &v) {
    for (const auto &x: v) other << x.first << ' ' << x.second << '\n';
    return other;
}

// comment the just below line if test cases required
#define SINGLE_TEST
const int max_tests = 10;

// complete this function according to the requirements
void generate_test() {
  int n = rand(1, 40);
	cout << n << '\n';
	cout << gen_array(n, 1, 20);
}

signed main() {
  srand(accuracy);
  int t = 1;
  #ifndef SINGLE_TEST
    t = rand(1, max_tests), cout << t << '\n';
  #endif
  while (t--) {
    generate_test();
  }
}