function readInputAndRunTED(arr) {
    let input = arr.slice();

    let insertCost = Number.parseInt(input.shift());
    let relabelCost = Number.parseInt(input.shift());
    let delCost = Number.parseInt(input.shift());

    // read labels
    let aElements = input.shift().split(' ');
    let aElementsSet = new Set(aElements);
    let bElements = input.shift().split(' ');
    let bElementsSet = new Set(bElements);

    //create base label to index mapping for A
    let aLabelToIndexMap = new Map();
    aElements.forEach((e, i) => aLabelToIndexMap.set(e, i));

    //create a label to index mapping for B
    let bLabelToIndexMap = new Map();
    bElements.forEach((e, i) => bLabelToIndexMap.set(e, i));

    // create A adjacency list
    let aAdjList = new Array(aElements.length).fill(undefined);
    let aEdgesCount = Number.parseInt(input.shift());
    let aEdgesArr = input.slice(0, aEdgesCount);
    input = input.slice(aEdgesCount);
    // fill A adjacency list
    for (let i = 0; i < aEdgesCount; i++) {
        let pairs = aEdgesArr[i].split(' ');
        let parentLabel = pairs[0];
        let childLabel = pairs[1];

        //while reading edges, remove each child from the set, the leftover node will be the root
        aElementsSet.delete(childLabel);

        let parentIndex = aLabelToIndexMap.get(parentLabel);
        let childIndex = aLabelToIndexMap.get(childLabel);
        if (aAdjList[parentIndex] === undefined) {
            aAdjList[parentIndex] = [];
        }
        aAdjList[parentIndex].push(childIndex);
    }


    // create left to right pre order of the elements
    let aRoot = aElementsSet.values().next().value;
    let aRootIndex = aElements.indexOf(aRoot);
    let aPreOrderElements = [];
    let aPreOrderAdjList = new Array(aElements.length).fill(undefined);
    preorderTraversal(aElements, aAdjList, aRootIndex, aPreOrderElements, aPreOrderAdjList, undefined);

    // create B adjacency list
    let bAdjList = new Array(bElements.length).fill(undefined);
    let bEdgesCount = Number.parseInt(input.shift());
    let bEdgesArr = input.slice(0, bEdgesCount);
    input = input.slice(bEdgesCount);
    // fill B adjacency list
    for (let i = 0; i < bEdgesCount; i++) {
        let pairs = bEdgesArr[i].split(' ');
        let parentLabel = pairs[0];
        let childLabel = pairs[1];

        //while reading edges, remove each child from the set, the leftover node will be the root
        bElementsSet.delete(childLabel);

        let parentIndex = bLabelToIndexMap.get(parentLabel);
        let childIndex = bLabelToIndexMap.get(childLabel);
        if (bAdjList[parentIndex] === undefined) {
            bAdjList[parentIndex] = [];
        }
        bAdjList[parentIndex].push(childIndex);
    }

    // create left to right pre order of the elements
    let bRoot = bElementsSet.values().next().value;
    let bRootIndex = bElements.indexOf(bRoot);
    let bPreOrderElements = [];
    let bPreOrderAdjList = new Array(bElements.length).fill(undefined);
    preorderTraversal(bElements, bAdjList, bRootIndex, bPreOrderElements, bPreOrderAdjList, undefined);


    //implementation requires nodes to be preordered to work
    let res = treeEditDistanceSetup(aPreOrderElements, aPreOrderAdjList, bPreOrderElements, bPreOrderAdjList, insertCost, relabelCost, delCost);
    return res;


    function preorderTraversal(elements, adjList, curIndex, preOrderElements, preOrderAdjList, parentPreOrderIndex) {
        preOrderElements.push(elements[curIndex]);
        // calc current preorder index based on how many elements we've already added to the preorder arr
        let curPreOrderIndex = preOrderElements.length - 1;

        if (parentPreOrderIndex != undefined) {
            if (preOrderAdjList[parentPreOrderIndex] == undefined) {
                preOrderAdjList[parentPreOrderIndex] = [];
            }
            preOrderAdjList[parentPreOrderIndex].push(curPreOrderIndex);
        }

        if (adjList[curIndex] != undefined) {
            for (let i = 0; i < adjList[curIndex].length; i++) {
                let childIndex = adjList[curIndex][i];
                preorderTraversal(elements, adjList, childIndex, preOrderElements, preOrderAdjList, curPreOrderIndex);
            }
        }
    }


    /**
     * Based on Benjamin Paaßen's implementation of Zhang and Shasha (1989) algorithm: https://gitlab.ub.uni-bielefeld.de/bpaassen/python-edit-distances/-/blob/master/edist/ted.pyx
     * 
     * Copyright (C) 2019-2021
     * Benjamin Paaßen
     * AG Machine Learning
     * Bielefeld University
     * 
     * This program is free software: you can redistribute it and/or modify
     * it under the terms of the GNU General Public License as published by
     * the Free Software Foundation, either version 3 of the License, or
     * (at your option) any later version.
     *
     * This program is distributed in the hope that it will be useful,
     * but WITHOUT ANY WARRANTY; without even the implied warranty of
     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
     * GNU General Public License for more details.
     *
     * You should have received a copy of the GNU General Public License
     * along with this program.  If not, see <http://www.gnu.org/licenses/>.
     */
    function treeEditDistanceSetup(x_nodes, x_adj, y_nodes, y_adj, costInsert, costReplace, costDelete) {
        let m = x_nodes.length;
        let n = y_nodes.length;

        let x_orl = findOutermostRightLeaves(x_adj)
        let x_kr = findKeyroots(x_orl)
        let y_orl = findOutermostRightLeaves(y_adj)
        let y_kr = findKeyroots(y_orl)

        let D_forest = new Array(m + 1).fill(0);
        D_forest = D_forest.map(x => (new Array(n + 1)).fill(0));

        let D_tree = new Array(m).fill(0);
        D_tree = D_tree.map(x => (new Array(n)).fill(0));

        calulateTreeDistanceMatrix(x_orl, x_kr, y_orl, y_kr, D_forest, D_tree, x_nodes, y_nodes, costInsert, costDelete, costReplace);

        // reconstruct and print an optimal path (for debugging)
        // let path = [];
        // reconstructOptimalPath(x_orl, y_orl, D_forest, D_tree, Delta, path, 0, 0);
        // let labeledPath = path.map(x => {
        //     let labels = [x[0] === -1 ? 'None' : x_nodes[x[0]], x[1] === -1 ? 'None' : y_nodes[x[1]]];
        //     return labels;
        // });

        // console.log(labeledPath.map(x => x.join(' -> ')).join('\n'));

        return D_tree[0][0];
    }

    // the DP matrix used in this implementation is used in a reverse manner, so all loops are in decremental order
    function calulateTreeDistanceMatrix(x_orl, x_kr, y_orl, y_kr, D_forest, D_tree, x_nodes, y_nodes, costInsert, costDelete, costReplace) {
        let K = x_kr.length;
        let L = y_kr.length;

        // for each keyroot of A and B
        for (let k = 0; k < K; k++) {
            for (let l = 0; l < L; l++) {
                // because of the preorder, an entire subtreeX can be represented as the range between krX (smallest index in X) and orlX (highest index in X)
                let i_0 = x_kr[k];
                let j_0 = y_kr[l];
                let i_max = x_orl[i_0] + 1;
                let j_max = y_orl[j_0] + 1;

                D_forest[i_max][j_max] = 0.;
                // initialize costs for deleting current subtree's vertices in A
                for (let i = i_max - 1; i > i_0 - 1; i--) {
                    //Delete cost
                    let currentDeleteCost = costDelete * x_nodes[i].length;
                    D_forest[i][j_max] = currentDeleteCost + D_forest[i + 1][j_max];
                }

                // initialize costs dor inserting current subtree's vertices in B
                for (let j = j_max - 1; j > j_0 - 1; j--) {
                    //Insert cost
                    let currentInsertCost = costInsert * y_nodes[j].length;
                    D_forest[i_max][j] = currentInsertCost + D_forest[i_max][j + 1];
                }

                // for each element in the current keyroot subtree of A
                for (let i = i_max - 1; i > i_0 - 1; i--) {
                    //for each element in the current keyroot subtree of B
                    for (let j = j_max - 1; j > j_0 - 1; j--) {
                        let currentInsertCost = costInsert * y_nodes[j].length;
                        let currentDeleteCost = costDelete * x_nodes[i].length;

                        // if we're currently working with entire subtrees for both A and B
                        if ((x_orl[i] === i_max - 1) && (y_orl[j] === j_max - 1)) {
                            D_forest[i][j] = Math.min(standardStringEditDistance(x_nodes[i], y_nodes[j], costInsert, costDelete, costReplace) + D_forest[i + 1][j + 1], // replacement
                                currentDeleteCost + D_forest[i + 1][j], // deletion
                                currentInsertCost + D_forest[i][j + 1] // insertion
                            );
                            //save cost of converting one subtree into another, so it can be reused, when calculating costs of encapsulating subtree
                            D_tree[i][j] = D_forest[i][j];
                        } else {
                            D_forest[i][j] = Math.min(D_tree[i][j] + D_forest[x_orl[i] + 1][y_orl[j] + 1], // tree replacement
                                currentDeleteCost + D_forest[i + 1][j], // deletion
                                currentInsertCost + D_forest[i][j + 1] // insertion
                            );
                        }
                    }
                }
            }
        }
    }

    function findOutermostRightLeaves(adjList) {
        let m = adjList.length;
        let orl = new Array(m);
        orl.fill(-1);
        let r = undefined;
        for (let i = 0; i < m; i++) {
            r = i;
            while (true) {
                if (!adjList[r]) {
                    orl[i] = r;
                    break;
                }

                if (orl[r] >= 0) {
                    orl[i] = orl[r];
                    break;
                }

                //outermost right leaf node
                r = adjList[r][adjList[r].length - 1];
            }
        }
        return orl;
    }

    function findKeyroots(orl) {
        let m = orl.length;
        let kr = new Array(m);
        kr.fill(-1);
        let keyrootsCount = 0;
        let outermostRightLeaf = undefined;

        for (let i = 0; i < m; i++) {
            outermostRightLeaf = orl[i];
            if (kr[outermostRightLeaf] < 0) {
                kr[outermostRightLeaf] = i;
                keyrootsCount += 1;
            }
        }

        let keyroots = new Array(keyrootsCount);
        keyroots.fill(0);

        let j = undefined;
        let i = 0;

        // Insertion sort
        for (let k = 0; k < keyrootsCount; k++) {
            while (kr[i] < 0) {
                i += 1;
            }

            j = k;
            while (j > 0 && keyroots[j - 1] < kr[i]) {
                keyroots[j] = keyroots[j - 1];
                j -= 1;
            }

            keyroots[j] = kr[i];
            i += 1;
        }

        return keyroots;
    }

    function standardStringEditDistance(a, b, costInsert, costDelete, costReplace) {
        let distances = new Array(a.length + 1).fill(0);
        distances = distances.map(x => (new Array(b.length + 1).fill(0)));

        for (let aIndex = 1; aIndex <= a.length; aIndex++) {
            distances[aIndex][0] = distances[aIndex - 1][0] + costDelete;
        }

        for (let bIndex = 1; bIndex <= b.length; bIndex++) {
            distances[0][bIndex] = distances[0][bIndex - 1] + costInsert;
        }

        for (let i = 1; i <= a.length; i++) {
            for (let j = 1; j <= b.length; j++) {
                let currentReplaceCost = a[i - 1] === b[j - 1] ? 0 : costReplace;
                distances[i][j] = Math.min(
                    distances[i - 1][j - 1] + currentReplaceCost,
                    distances[i - 1][j] + costDelete,
                    distances[i][j - 1] + costInsert
                );
            }
        }

        return distances[a.length][b.length];
    }
}