#!/usr/bin/env python3
#
# Testing tool for the Hansel and Gretel problem
#
# Usage:
#
#   python3 testing_tool.py -f <input file> <program invocation>
#
#
# Use the -f parameter to specify the input file, e.g. 1.in.
# The input file may contain the input for the first pass as described in the input section.

# You can compile and run your solution as follows:

# C++:
#   g++ solution.cpp
#   python3 testing_tool.py -f 1.in ./a.out

# Python:
#   python3 testing_tool.py -f 1.in python3 ./solution.py

# Java:
#   javac solution.java
#   python3 testing_tool.py -f 1.in java solution

# Haskell:
#   ghc solution.hs
#   python3 testing_tool.py -f 1.in ./solution


# The tool is provided as-is, and you should feel free to make
# whatever alterations or augmentations you like to it.
#
# The tool attempts to detect and report common errors, but it is not an exhaustive test.
# It is not guaranteed that a program that passes this testing tool will be accepted.


import argparse
import subprocess
import traceback
import random

parser = argparse.ArgumentParser(description="Testing tool for problem Hansel and Gretel.")
parser.add_argument(
    "-f",
    dest="inputfile",
    metavar="inputfile",
    default=None,
    type=argparse.FileType("r"),
    required=False,
    help="The input file to use.",
)
parser.add_argument("program", nargs="+", help="Invocation of your solution")

args = parser.parse_args()

# parse input graph
assert args.inputfile is not None, "No input file given"
inputfile = args.inputfile.read()

parsed_input = inputfile.split()
pass_number = parsed_input[0]

assert pass_number == '1', "The input must be for the first pass"

n, m = int(parsed_input[1]), int(parsed_input[2])

adj = [[] for _ in range(n)]
input_edges = parsed_input[3:]
for i in range(0, len(input_edges), 2):
    a, b = int(input_edges[i]), int(input_edges[i + 1])
    assert a >= 1 and a <= n, "Invalid pathway"
    assert b >= 1 and b <= n, "Invalid pathway"

    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

try:
    # First pass
    output = subprocess.check_output(
        " ".join(args.program),
        shell=True,
        input=inputfile,
        universal_newlines=True).strip()
    print(f"Output of first pass:\n{output}\n")

    try:
        output = list(map(int, output.split()))
    except ValueError:
        assert False, "Invalid output format"

    edgecount = output[0]
    edges = output[1:]

    assert edgecount == len(edges), "Number of pathways does not match pathways in output"
    assert len(set(edges)) == len(edges), "No duplicate pathways allowed"

    # add new vertex
    adj.append([])
    for edge in edges:
        assert edge >= 1 and edge <= n, "Invalid edge"
        adj[edge - 1].append(n)
        adj[n].append(edge - 1)

    # Shuffle graph labels
    permutation = list(range(n + 1))
    random.shuffle(permutation)

    # build input for second pass
    second_pass_edgelist = []
    for x in range(n + 1):
        for y in adj[x]:
            if x < y:
                # don't output duplicate edges
                continue
            l, r = permutation[x] + 1, permutation[y] + 1
            # randomly swap left and right entry of edge
            if random.choice([True, False]):
                l, r = r, l
            second_pass_edgelist.append(f"{l} {r}")
    random.shuffle(second_pass_edgelist)

    second_pass_input = "2\n"
    second_pass_input += f"{n + 1} {m + edgecount}\n"
    second_pass_input += "\n".join(second_pass_edgelist)

    print("Shuffled labels:")
    for x, y in enumerate(permutation):
        print(x + 1, '->', y + 1)
    print(f"Running second pass with input:\n{second_pass_input}\n")

    output = subprocess.check_output(
        " ".join(args.program),
        shell=True,
        input=second_pass_input,
        universal_newlines=True).strip()
    print(f"Output of second pass:\n{output}\n")

    try:
        node = int(output)
    except ValueError:
        assert False, "Output of second pass is not a single number"

    if node == permutation[n] + 1:
        print()
        print("Correctly identified the added clearing.", flush=True)
    else:
        print()
        print("Wrong clearing selected.", flush=True)

except AssertionError as e:
    print()
    print(f"Error: {e}")
    exit(1)

except Exception:
    print()
    print("Unexpected error:")
    traceback.print_exc()
    exit(1)