#!/bin/bash

# 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);

CPP_VERSION="c++17"
COMPILE_FLAGS=""
TC_GENERATOR_FILE="tc_generator.cpp"
MAX_TESTS="10"

BRUTE_FILE=""
MAIN_FILE=""

############################################################
# USAGE
usage(){
  echo "
USAGE:
      $$$(basename &quot;$$${0}") -b <brute-sol> -m <main-sol> [ -t <no.-of-testcases> ]
  Options:
      -b <brute-file>     Specify the name of cpp file having brute force solution. [required]
      -m <main-file>      Specify the name of cpp file having main solution. [required]
      -t <integer>        No. of test cases to generate and stress test on. (optional, default 10)
"
}

# Checks if the main, brute and generator files exists or not.
function check_files_exists() {
    declare -a cpp_files=("$1" "$2" "$3")
    for file in "${cpp_files[@]}"; do
        # echo "${file}"
        if ! [[ -f "$file" ]]; then
            echo "File $$${orange}$$${file}$$${reset} does not exist in dir $$$(pwd), exiting..."
            exit 1
        fi
    done
}

# Compiles a given cpp file and stores the executable in variable `executable_fname`
function compile() {
    local cpp_file="$1"
    local executable_fname="$2"

    local start_time="$(date +%s)"
    g++ -std="$$${CPP_VERSION}&quot; &quot;$$${cpp_file}" -o "$$${executable_fname}&quot; &quot;$$${COMPILE_FLAGS}" || { echo "$$${bold}$$${red}Error when compiling: $$${reset}$$${orange}$$${cpp_file}$$${reset}"; exit 1; }
    local end_time="$(date +%s)"

    echo "$$${green}Successfully compiled $$${cpp_file}$$${reset} in $$${orange}$$$((end_time - start_time))s$$${reset}."
}

function cleanup() {
    rm -f input1.txt generator original brute original_output.txt brute_output.txt
}

function tips() {
    echo ""
    echo "$$${blue}You might want to use $$${green}https://www.diffchecker.com/diff${reset} to better visualize the difference in output :)${reset}"
}

function stress_test() {
    local diff_found=0

    echo "" && echo "Starting stress testing on $$${orange}$$${MAX_TESTS}${reset} randomly generated test cases:" && echo ""

    for ((i=0; i<$MAX_TESTS; i++)); 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 #|| {echo failed; exit 1;}

        # 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 -F --label --side-by-side --ignore-space-change original_output.txt brute_output.txt > /dev/null; then
            echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${green}passed$$${reset}"
        else
            echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${red}failed$$${reset}"
            diff_found=1
            break
        fi
    done

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

        echo "$$${blue}Output(Main sol): $$${reset}"
        cat original_output.txt
        echo ""; echo ""

        echo "$$${blue}Expected(Brute sol): $$${reset}"
        cat brute_output.txt
        echo ""

        tips
    fi
}

function main() {
    # Parse args
    while [[ $# -gt 0 ]]; do
    case $1 in
        -b)
        BRUTE_FILE="$2"
        shift # past argument
        shift # past value
        ;;
        -m)
        MAIN_FILE="$2"
        shift
        shift
        ;;
        -h)
        usage
        exit
        ;;
        -t)
        MAX_TESTS="$2"
        re='^[0-9]+$'
        if ! [[ $MAX_TESTS =~ $re ]] ; then
            echo "error: argument -t must be a number e.g. -t 69 "; exit 1
        fi
        shift
        shift
        ;;
        -*|--*)
        echo "Unknown option $1"
        exit 1
        ;;
    esac
    done

    check_files_exists "$$${BRUTE_FILE}&quot; &quot;$$${MAIN_FILE}" "${TC_GENERATOR_FILE}"
    compile "${TC_GENERATOR_FILE}" "generator"
    compile "${MAIN_FILE}" "original"
    compile "${BRUTE_FILE}" "brute"

    stress_test
}

main "$@"

#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();
  }
}