/*
 * (C) Copyright 2018-2023, by Timofey Chudakov and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * See the CONTRIBUTORS.md file distributed with this work for additional
 * information regarding copyright ownership.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Public License 2.0 which is available at
 * http://www.eclipse.org/legal/epl-2.0, or the
 * GNU Lesser General Public License v2.1 or later
 * which is available at
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1-standalone.html.
 *
 * SPDX-License-Identifier: EPL-2.0 OR LGPL-2.1-or-later
 */
package org.jgrapht.alg.matching.blossom.v5;

import org.jgrapht.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.graph.*;
import org.jgrapht.util.*;
import org.junit.*;
import org.junit.runner.*;
import org.junit.runners.*;

import static junit.framework.TestCase.assertEquals;
import static junit.framework.TestCase.assertTrue;
import static org.jgrapht.alg.matching.blossom.v5.KolmogorovWeightedPerfectMatching.EPS;
import static org.jgrapht.alg.matching.blossom.v5.ObjectiveSense.MAXIMIZE;
import static org.jgrapht.alg.matching.blossom.v5.ObjectiveSense.MINIMIZE;

/**
 * Unit tests for the {@link KolmogorovWeightedMatching}
 *
 * @author Timofey Chudakov
 */
@RunWith(Parameterized.class)

public class KolmogorovWeightedMatchingTest
{
    /**
     * Algorithm options
     */
    private BlossomVOptions options;
    /**
     * Objective sense of the algorithm
     */
    private ObjectiveSense objectiveSense;

    public KolmogorovWeightedMatchingTest(BlossomVOptions options, ObjectiveSense objectiveSense)
    {
        this.options = options;
        this.objectiveSense = objectiveSense;
    }

    /**
     * Generate all combinations of options and algorithm objective sense.
     *
     * @return all combinations of options and algorithm objective sense.
     */
    @Parameterized.Parameters
    public static Object[][] params()
    {
        BlossomVOptions[] options = BlossomVOptions.ALL_OPTIONS;
        Object[][] params = new Object[2 * options.length][2];
        for (int i = 0; i < options.length; i++) {
            params[2 * i][0] = options[i];
            params[2 * i][1] = MAXIMIZE;
            params[2 * i + 1][0] = options[i];
            params[2 * i + 1][1] = MINIMIZE;
        }
        return params;
    }

    @Test
    public void testGetMatching1()
    {
        int[][] edges = new int[][] { { 0, 1, -1 }, { 1, 2, 1 }, { 2, 3, -1 }, { 3, 0, 1 }, };
        double maxWeight = 2;
        double minWeight = -2;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    @Test
    public void testGetMatching2()
    {
        int[][] edges = new int[][] { { 0, 1, 3 }, { 1, 2, 2 }, { 2, 3, 1 }, { 3, 0, 5 },
            { 0, 2, 15 }, { 1, 3, -15 } };
        double maxWeight = 15;
        double minWeight = -15;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Triangulation of 3 points with randomly negated edge weights
     */
    @Test
    public void testGetMatching3()
    {
        int[][] edges = new int[][] { { 2, 0, -2 }, { 1, 2, 2 }, { 0, 1, 3 }, };
        double maxWeight = 3;
        double minWeight = -2;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Triangulation of 10 points with randomly negated edge weights
     */
    @Test
    public void testGetMatching4()
    {
        int[][] edges = new int[][] { { 9, 4, 4 }, { 7, 9, 4 }, { 4, 7, -4 }, { 6, 4, -2 },
            { 9, 6, 2 }, { 8, 9, -2 }, { 6, 8, 1 }, { 4, 5, 3 }, { 6, 3, 3 }, { 1, 6, 6 },
            { 3, 4, 1 }, { 4, 2, -5 }, { 3, 2, 5 }, { 0, 2, -1 }, { 8, 1, 7 }, { 0, 1, -6 },
            { 3, 0, -5 }, { 1, 3, -3 }, { 5, 7, -2 }, { 2, 5, 4 }, { 7, 2, -6 }, };
        double maxWeight = 19;
        double minWeight = -16;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Triangulation of 10 points with randomly negated edge weights
     */
    @Test
    public void testGetMatching5()
    {
        int[][] edges = new int[][] { { 9, 5, 4 }, { 8, 9, -4 }, { 8, 5, -4 }, { 5, 7, 4 },
            { 6, 7, 2 }, { 5, 6, -4 }, { 8, 4, 4 }, { 3, 8, -4 }, { 5, 2, 3 }, { 7, 9, 2 },
            { 5, 0, -5 }, { 4, 5, -3 }, { 4, 0, 5 }, { 1, 0, -5 }, { 2, 6, 1 }, { 0, 2, -5 },
            { 4, 1, 2 }, { 3, 4, -1 }, { 1, 3, 2 }, { 0, 6, 6 }, };
        double maxWeight = 17;
        double minWeight = -14;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Triangulation of 50 points with randomly negated edge weights
     */
    @Test
    public void testGetMatching6()
    {
        int[][] edges = new int[][] { { 48, 49, 30 }, { 48, 47, -30 }, { 48, 42, 17 },
            { 48, 40, 17 }, { 45, 40, -19 }, { 43, 44, 8 }, { 47, 49, 2 }, { 34, 47, 27 },
            { 49, 34, 29 }, { 41, 44, -20 }, { 46, 41, 13 }, { 44, 46, -14 }, { 45, 38, -14 },
            { 41, 45, -9 }, { 38, 40, -11 }, { 41, 38, 7 }, { 36, 41, 8 }, { 42, 39, 7 },
            { 40, 42, 6 }, { 39, 40, -2 }, { 48, 45, 17 }, { 46, 48, 20 }, { 45, 46, 5 },
            { 35, 44, -16 }, { 44, 36, 20 }, { 35, 37, 18 }, { 43, 35, 13 }, { 37, 43, 15 },
            { 33, 42, 13 }, { 47, 33, -27 }, { 42, 47, 26 }, { 39, 33, -17 }, { 28, 39, 20 },
            { 33, 34, 27 }, { 31, 35, 13 }, { 33, 30, 30 }, { 37, 31, -12 }, { 39, 25, 21 },
            { 38, 39, 10 }, { 25, 38, 20 }, { 35, 36, 13 }, { 32, 35, 3 }, { 30, 34, 8 },
            { 36, 26, -16 }, { 32, 36, -12 }, { 32, 26, -22 }, { 31, 32, 12 }, { 29, 31, -6 },
            { 33, 17, 30 }, { 28, 33, -10 }, { 32, 22, -23 }, { 29, 32, -10 }, { 38, 27, 17 },
            { 36, 38, -11 }, { 27, 36, -16 }, { 31, 23, 12 }, { 21, 31, 16 }, { 26, 24, 6 },
            { 22, 26, -10 }, { 28, 17, -26 }, { 17, 30, -20 }, { 37, 21, 25 }, { 23, 29, -10 },
            { 25, 26, -10 }, { 27, 25, -9 }, { 26, 27, 1 }, { 25, 9, 27 }, { 21, 23, -7 },
            { 23, 19, 16 }, { 14, 23, -20 }, { 29, 22, -21 }, { 19, 29, 17 }, { 28, 13, -20 },
            { 22, 24, -4 }, { 21, 14, -25 }, { 6, 21, -28 }, { 22, 18, -4 }, { 19, 22, 7 },
            { 18, 19, 8 }, { 24, 25, 12 }, { 18, 24, -6 }, { 25, 18, -18 }, { 16, 25, -18 },
            { 28, 16, -16 }, { 25, 28, 16 }, { 19, 15, -5 }, { 14, 19, 5 }, { 16, 13, 11 },
            { 20, 30, 14 }, { 30, 11, -28 }, { 15, 18, 5 }, { 6, 14, -34 }, { 10, 14, -13 },
            { 15, 10, -12 }, { 14, 15, -1 }, { 17, 20, 6 }, { 20, 11, 14 }, { 8, 13, -17 },
            { 17, 11, 13 }, { 12, 11, -18 }, { 12, 13, 4 }, { 17, 12, 13 }, { 13, 17, 13 },
            { 16, 8, -16 }, { 37, 6, -53 }, { 2, 11, -29 }, { 16, 7, -24 }, { 9, 16, -24 },
            { 9, 7, 4 }, { 5, 9, -11 }, { 9, 10, -8 }, { 18, 9, 19 }, { 10, 18, -13 },
            { 10, 5, 18 }, { 10, 0, 37 }, { 6, 10, 37 }, { 8, 12, -15 }, { 2, 8, 16 },
            { 12, 2, -24 }, { 8, 4, 16 }, { 7, 8, 17 }, { 1, 4, -12 }, { 4, 2, -19 }, { 5, 1, 18 },
            { 0, 5, 38 }, { 0, 1, -53 }, { 4, 5, -6 }, { 7, 4, 11 }, { 5, 7, 8 }, { 6, 0, -16 },
            { 3, 6, 5 }, { 0, 3, 12 }, { 1, 2, -10 }, };
        double maxWeight = 417;
        double minWeight = -436;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Triangulation of 100 points with randomly negated edge weights
     */
    @Test
    public void testGetMatching7()
    {
        int[][] edges = new int[][] { { 97, 99, 28 }, { 99, 96, -17 }, { 99, 93, -15 },
            { 98, 99, -25 }, { 96, 94, -16 }, { 95, 97, -24 }, { 99, 92, -44 }, { 94, 99, 33 },
            { 98, 86, 20 }, { 94, 92, 11 }, { 95, 90, -16 }, { 94, 91, 5 }, { 91, 92, 6 },
            { 88, 94, 11 }, { 94, 89, 4 }, { 93, 96, 2 }, { 96, 88, 8 }, { 95, 87, -15 },
            { 91, 79, -13 }, { 89, 91, 4 }, { 93, 88, -9 }, { 89, 79, -13 }, { 90, 97, 10 },
            { 85, 97, -12 }, { 97, 98, 3 }, { 95, 80, 14 }, { 89, 77, -13 }, { 87, 90, 3 },
            { 90, 85, 11 }, { 78, 93, 15 }, { 93, 84, 12 }, { 99, 78, -20 }, { 86, 99, -15 },
            { 86, 78, -17 }, { 89, 69, 18 }, { 88, 89, -11 }, { 83, 85, 7 }, { 98, 83, -16 },
            { 85, 98, 12 }, { 80, 87, 14 }, { 87, 81, 8 }, { 86, 75, 8 }, { 83, 86, 12 },
            { 87, 85, -12 }, { 82, 87, 8 }, { 85, 82, 9 }, { 83, 75, -14 }, { 92, 22, 61 },
            { 79, 92, -13 }, { 83, 64, -15 }, { 82, 83, -14 }, { 64, 82, -17 }, { 84, 88, -10 },
            { 82, 63, 14 }, { 81, 82, 1 }, { 79, 22, -48 }, { 84, 76, 5 }, { 88, 69, -18 },
            { 76, 88, 12 }, { 78, 84, -7 }, { 74, 78, 3 }, { 84, 74, -7 }, { 76, 69, -13 },
            { 78, 72, 6 }, { 75, 78, 14 }, { 78, 71, 8 }, { 80, 81, 15 }, { 73, 80, -4 },
            { 76, 67, 8 }, { 64, 75, 21 }, { 76, 68, -9 }, { 74, 76, 8 }, { 75, 71, -10 },
            { 70, 75, -5 }, { 71, 72, 3 }, { 54, 80, 21 }, { 80, 65, 13 }, { 71, 68, -9 },
            { 71, 57, -13 }, { 68, 72, -6 }, { 74, 68, 6 }, { 72, 74, -5 }, { 68, 67, 6 },
            { 57, 68, 8 }, { 69, 77, 11 }, { 66, 69, -4 }, { 77, 66, 13 }, { 67, 69, 12 },
            { 69, 62, -6 }, { 67, 62, -10 }, { 65, 73, -9 }, { 81, 63, 14 }, { 73, 81, 13 },
            { 61, 73, 13 }, { 73, 63, 15 }, { 71, 48, -16 }, { 65, 61, -6 }, { 66, 60, 5 },
            { 62, 66, 3 }, { 62, 60, -7 }, { 79, 46, 29 }, { 53, 63, 12 }, { 63, 64, 12 },
            { 59, 63, -8 }, { 54, 65, -8 }, { 65, 58, -4 }, { 70, 47, 24 }, { 64, 70, 21 },
            { 54, 58, 4 }, { 62, 52, -8 }, { 55, 62, -12 }, { 61, 63, 6 }, { 48, 57, -10 },
            { 95, 54, 35 }, { 57, 67, 9 }, { 55, 57, 5 }, { 67, 55, 9 }, { 56, 58, 1 },
            { 58, 61, -5 }, { 55, 52, -10 }, { 61, 49, 7 }, { 56, 61, -4 }, { 60, 46, 13 },
            { 52, 60, 10 }, { 64, 47, -10 }, { 50, 64, -9 }, { 52, 46, -11 }, { 45, 53, -8 },
            { 53, 50, 2 }, { 51, 48, 4 }, { 54, 56, 4 }, { 49, 54, 4 }, { 56, 49, 5 },
            { 64, 53, -8 }, { 59, 64, 5 }, { 53, 59, -5 }, { 51, 70, -15 }, { 71, 51, 15 },
            { 70, 71, -6 }, { 45, 50, 8 }, { 50, 47, 3 }, { 52, 44, 10 }, { 49, 63, -12 },
            { 45, 49, -17 }, { 63, 45, 17 }, { 60, 77, 14 }, { 79, 60, 17 }, { 77, 79, -3 },
            { 51, 43, -11 }, { 55, 36, -18 }, { 27, 49, 23 }, { 49, 42, -17 }, { 46, 22, -20 },
            { 51, 41, 15 }, { 47, 51, 20 }, { 37, 44, 8 }, { 47, 41, 14 }, { 36, 52, -15 },
            { 52, 37, -15 }, { 13, 54, -40 }, { 54, 27, -26 }, { 47, 39, -13 }, { 45, 47, 10 },
            { 45, 39, 13 }, { 41, 43, 15 }, { 43, 34, 7 }, { 48, 55, -14 }, { 43, 48, 9 },
            { 34, 40, -5 }, { 44, 46, -5 }, { 46, 26, 16 }, { 55, 40, 19 }, { 43, 55, 18 },
            { 40, 43, -5 }, { 38, 44, -6 }, { 44, 26, -14 }, { 40, 36, -16 }, { 38, 26, -12 },
            { 24, 41, -16 }, { 41, 34, 14 }, { 35, 40, -4 }, { 40, 31, -7 }, { 34, 35, -1 },
            { 24, 34, 8 }, { 42, 45, -3 }, { 33, 42, 10 }, { 45, 33, -11 }, { 33, 39, -6 },
            { 25, 33, -12 }, { 24, 35, 9 }, { 35, 31, 8 }, { 41, 19, -16 }, { 39, 41, 6 },
            { 31, 36, 11 }, { 39, 19, -17 }, { 32, 39, 6 }, { 28, 36, -9 }, { 31, 28, -4 },
            { 29, 36, -7 }, { 37, 29, -8 }, { 36, 37, 1 }, { 33, 32, 1 }, { 30, 33, 2 },
            { 28, 29, -2 }, { 29, 20, -8 }, { 20, 37, 13 }, { 38, 20, -13 }, { 37, 38, -3 },
            { 32, 19, 18 }, { 30, 32, 1 }, { 26, 22, 6 }, { 27, 23, 3 }, { 25, 27, 4 },
            { 42, 25, 13 }, { 27, 42, -13 }, { 30, 19, -18 }, { 17, 28, 12 }, { 28, 20, -9 },
            { 13, 27, 21 }, { 27, 21, -4 }, { 31, 17, -14 }, { 24, 31, 14 }, { 30, 14, -20 },
            { 23, 25, 3 }, { 21, 23, -1 }, { 26, 18, -9 }, { 20, 26, -15 }, { 30, 11, -22 },
            { 20, 18, -12 }, { 13, 21, 19 }, { 18, 22, -10 }, { 19, 24, -6 }, { 24, 17, 15 },
            { 18, 8, -12 }, { 4, 18, -21 }, { 8, 4, 20 }, { 19, 17, -19 }, { 14, 19, -8 },
            { 15, 6, -11 }, { 21, 25, -4 }, { 16, 21, -7 }, { 17, 20, -11 }, { 15, 17, 2 },
            { 30, 10, -22 }, { 25, 30, -11 }, { 15, 20, -10 }, { 4, 15, 17 }, { 20, 4, 22 },
            { 95, 13, -75 }, { 14, 17, -23 }, { 17, 6, 12 }, { 0, 13, -17 }, { 7, 0, 13 },
            { 25, 10, -17 }, { 16, 25, 10 }, { 7, 13, 10 }, { 12, 7, -6 }, { 12, 13, 14 },
            { 13, 16, -15 }, { 12, 16, -6 }, { 16, 10, -9 }, { 11, 14, 7 }, { 14, 6, 26 },
            { 12, 10, -7 }, { 5, 12, 8 }, { 2, 11, -20 }, { 6, 2, 46 }, { 11, 6, -30 },
            { 5, 10, -6 }, { 9, 5, -6 }, { 22, 1, 29 }, { 8, 22, 16 }, { 1, 8, 13 }, { 9, 10, -1 },
            { 11, 9, -14 }, { 10, 11, 15 }, { 5, 7, 9 }, { 0, 5, 16 }, { 6, 4, -9 }, { 2, 5, 6 },
            { 9, 2, 11 }, { 4, 3, 16 }, { 3, 8, -9 }, { 1, 3, 5 }, { 1, 0, -89 }, { 0, 2, 16 },
            { 4, 1, 19 }, { 2, 4, 54 }, { 1, 2, 73 }, };
        double maxWeight = 731;
        double minWeight = -745;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 4 vertices and 4 edges
     */
    @Test
    public void testGetMatching8()
    {
        int[][] edges = new int[][] { { 0, 1, 7 }, { 3, 2, 9 }, { 3, 0, -8 }, { 1, 2, 7 }, };
        double maxWeight = 16;
        double minWeight = -8;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 10 vertices and 20 edges
     */
    @Test
    public void testGetMatching9()
    {
        int[][] edges = new int[][] { { 0, 7, 10 }, { 8, 1, 10 }, { 0, 9, 10 }, { 6, 3, 10 },
            { 8, 5, 10 }, { 3, 1, 1 }, { 8, 6, -7 }, { 7, 6, -5 }, { 5, 3, 1 }, { 1, 2, -8 },
            { 9, 6, -4 }, { 9, 8, 3 }, { 9, 5, -6 }, { 2, 7, 9 }, { 6, 1, 10 }, { 8, 3, -8 },
            { 6, 2, 7 }, { 3, 2, 9 }, { 8, 7, -8 }, { 5, 1, 7 }, };
        double maxWeight = 39;
        double minWeight = -27;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 15 vertices and 40 edges
     */
    @Test
    public void testGetMatching10()
    {
        int[][] edges = new int[][] { { 3, 1, 0 }, { 8, 13, 10 }, { 10, 14, 8 }, { 5, 14, 6 },
            { 8, 7, 3 }, { 11, 8, 9 }, { 10, 6, -8 }, { 5, 8, -2 }, { 1, 8, -10 }, { 10, 9, -8 },
            { 3, 7, -4 }, { 4, 6, 6 }, { 9, 12, 6 }, { 10, 11, 0 }, { 2, 1, -8 }, { 5, 3, 10 },
            { 2, 0, 10 }, { 13, 3, 10 }, { 9, 4, 5 }, { 5, 13, -7 }, { 14, 8, 10 }, { 4, 3, 10 },
            { 10, 3, 10 }, { 1, 12, 10 }, { 4, 7, 10 }, { 8, 9, 1 }, { 8, 10, -7 }, { 12, 11, -5 },
            { 13, 10, 1 }, { 6, 3, -8 }, { 14, 7, -4 }, { 11, 3, 3 }, { 1, 6, -6 }, { 13, 1, 9 },
            { 11, 13, 10 }, { 13, 6, -8 }, { 1, 14, 7 }, { 6, 7, 9 }, { 2, 5, -8 }, { 0, 4, 7 }, };
        double maxWeight = 64;
        double minWeight = -43;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 30 vertices and 100 edges
     */
    @Test
    public void testGetMatching11()
    {
        int[][] edges = new int[][] { { 19, 24, 6 }, { 29, 23, 5 }, { 14, 27, 9 }, { 29, 14, 4 },
            { 25, 12, 6 }, { 21, 22, 3 }, { 16, 23, 0 }, { 20, 9, -1 }, { 6, 17, -1 }, { 3, 19, 0 },
            { 27, 5, -2 }, { 3, 6, -7 }, { 24, 17, -10 }, { 3, 23, 6 }, { 29, 15, -9 },
            { 9, 13, 6 }, { 13, 15, -6 }, { 4, 15, -2 }, { 23, 26, -8 }, { 9, 14, -1 },
            { 1, 27, 3 }, { 16, 13, -10 }, { 6, 1, 0 }, { 12, 15, 9 }, { 27, 29, 6 }, { 6, 0, -4 },
            { 13, 25, -8 }, { 26, 28, 4 }, { 8, 6, 7 }, { 10, 15, 7 }, { 28, 5, 10 },
            { 13, 14, -8 }, { 19, 9, -7 }, { 14, 28, -10 }, { 1, 19, 8 }, { 6, 21, -5 },
            { 27, 3, -4 }, { 12, 20, -10 }, { 1, 25, 6 }, { 20, 27, 4 }, { 12, 8, -4 },
            { 3, 15, -7 }, { 0, 25, -7 }, { 17, 5, 3 }, { 24, 22, -2 }, { 1, 16, -2 },
            { 27, 26, -1 }, { 5, 18, 5 }, { 8, 18, 5 }, { 3, 28, 5 }, { 19, 8, -2 }, { 10, 2, 4 },
            { 13, 18, 4 }, { 2, 23, 9 }, { 28, 6, -6 }, { 5, 20, 7 }, { 23, 1, -3 },
            { 21, 16, -10 }, { 29, 0, 6 }, { 2, 15, 3 }, { 16, 26, 0 }, { 4, 10, 10 }, { 28, 7, 8 },
            { 12, 2, 6 }, { 11, 29, 3 }, { 3, 24, 9 }, { 1, 2, -8 }, { 28, 0, -2 }, { 13, 17, -10 },
            { 2, 19, -8 }, { 21, 10, -4 }, { 6, 4, 6 }, { 1, 13, 6 }, { 9, 24, 0 }, { 28, 21, -8 },
            { 21, 18, 10 }, { 4, 27, 10 }, { 21, 9, 10 }, { 17, 20, 5 }, { 5, 15, -7 },
            { 9, 2, 10 }, { 20, 24, 10 }, { 16, 28, 10 }, { 8, 4, 10 }, { 22, 13, 10 },
            { 11, 28, 1 }, { 4, 16, -7 }, { 20, 18, -5 }, { 16, 12, 1 }, { 25, 14, -8 },
            { 7, 19, -4 }, { 25, 4, 3 }, { 7, 11, -6 }, { 22, 19, 9 }, { 2, 6, 10 }, { 5, 14, -8 },
            { 1, 11, 7 }, { 9, 18, 9 }, { 17, 3, -8 }, { 7, 3, 7 }, };
        double maxWeight = 112;
        double minWeight = -98;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 50 vertices and 100 edges
     */
    @Test
    public void testGetMatching12()
    {
        int[][] edges = new int[][] { { 7, 28, 6 }, { 6, 29, 5 }, { 32, 5, 9 }, { 4, 27, 4 },
            { 23, 4, 6 }, { 25, 43, 3 }, { 36, 19, 0 }, { 37, 36, -1 }, { 33, 25, -1 },
            { 37, 47, 0 }, { 46, 17, -2 }, { 30, 47, -7 }, { 20, 3, -10 }, { 15, 45, 6 },
            { 30, 39, -9 }, { 26, 29, 6 }, { 16, 5, -6 }, { 9, 3, -2 }, { 30, 44, -8 },
            { 36, 27, -1 }, { 28, 1, 3 }, { 40, 44, -10 }, { 24, 27, 0 }, { 30, 21, 9 },
            { 7, 19, 6 }, { 0, 10, -4 }, { 5, 8, -8 }, { 6, 26, 4 }, { 28, 36, 7 }, { 12, 7, 7 },
            { 13, 11, 10 }, { 2, 5, -8 }, { 11, 30, -7 }, { 47, 12, -10 }, { 20, 43, 8 },
            { 3, 48, -5 }, { 42, 34, -4 }, { 24, 35, -10 }, { 31, 41, 6 }, { 6, 9, 4 },
            { 0, 13, -4 }, { 35, 31, -7 }, { 14, 32, -7 }, { 35, 47, 3 }, { 37, 13, -2 },
            { 18, 23, -2 }, { 1, 47, -1 }, { 11, 6, 5 }, { 15, 12, 5 }, { 33, 1, 5 },
            { 33, 47, -2 }, { 42, 7, 4 }, { 47, 45, 4 }, { 14, 11, 9 }, { 27, 14, -6 },
            { 33, 27, 7 }, { 47, 29, -3 }, { 6, 21, -10 }, { 22, 7, 6 }, { 48, 12, 3 },
            { 32, 25, 0 }, { 41, 47, 10 }, { 9, 49, 8 }, { 47, 44, 6 }, { 4, 15, 3 }, { 38, 0, 9 },
            { 43, 16, -8 }, { 13, 22, -2 }, { 40, 16, -10 }, { 26, 22, -8 }, { 31, 1, -4 },
            { 38, 40, 6 }, { 8, 47, 6 }, { 34, 33, 0 }, { 11, 29, -8 }, { 48, 43, 10 },
            { 27, 16, 10 }, { 41, 49, 10 }, { 45, 0, 5 }, { 38, 45, -7 }, { 5, 29, 10 },
            { 34, 18, 10 }, { 14, 24, 10 }, { 16, 14, 10 }, { 13, 45, 10 }, { 18, 47, 1 },
            { 22, 4, -7 }, { 16, 41, -5 }, { 22, 19, 1 }, { 11, 33, -8 }, { 3, 28, -4 },
            { 18, 1, 3 }, { 40, 9, -6 }, { 7, 13, 9 }, { 4, 13, 10 }, { 43, 35, -8 }, { 46, 27, 7 },
            { 8, 20, 9 }, { 31, 18, -8 }, { 12, 18, 7 }, };
        double maxWeight = 146;
        double minWeight = -127;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 100 vertices and 100 edges
     */
    @Test
    public void testGetMatching13()
    {
        int[][] edges = new int[][] { { 98, 6, 6 }, { 53, 82, 5 }, { 0, 7, 9 }, { 57, 91, 4 },
            { 69, 41, 6 }, { 18, 15, 3 }, { 84, 38, 0 }, { 43, 57, -1 }, { 31, 81, -1 },
            { 84, 88, 0 }, { 6, 74, -2 }, { 74, 36, -7 }, { 69, 1, -10 }, { 7, 69, 6 },
            { 15, 67, -9 }, { 66, 70, 6 }, { 74, 43, -6 }, { 88, 97, -2 }, { 61, 78, -8 },
            { 26, 96, -1 }, { 3, 41, 3 }, { 41, 89, -10 }, { 0, 40, 0 }, { 82, 12, 9 },
            { 61, 62, 6 }, { 93, 60, -4 }, { 5, 4, -8 }, { 16, 23, 4 }, { 65, 30, 7 }, { 37, 3, 7 },
            { 61, 75, 10 }, { 58, 42, -8 }, { 60, 8, -7 }, { 96, 1, -10 }, { 86, 30, 8 },
            { 90, 52, -5 }, { 27, 83, -4 }, { 78, 24, -10 }, { 6, 34, 6 }, { 45, 14, 4 },
            { 95, 39, -4 }, { 36, 27, -7 }, { 78, 79, -7 }, { 2, 89, 3 }, { 28, 59, -2 },
            { 76, 5, -2 }, { 55, 78, -1 }, { 38, 93, 5 }, { 72, 35, 5 }, { 52, 78, 5 },
            { 92, 76, -2 }, { 52, 81, 4 }, { 4, 81, 4 }, { 85, 51, 9 }, { 12, 37, -6 },
            { 76, 32, 7 }, { 55, 47, -3 }, { 58, 9, -10 }, { 71, 67, 6 }, { 22, 56, 3 },
            { 32, 85, 0 }, { 28, 11, 10 }, { 75, 37, 8 }, { 18, 34, 6 }, { 94, 21, 3 },
            { 10, 42, 9 }, { 6, 0, -8 }, { 48, 20, -2 }, { 64, 48, -10 }, { 77, 62, -8 },
            { 69, 62, -4 }, { 76, 72, 6 }, { 1, 20, 6 }, { 11, 25, 0 }, { 33, 28, -8 },
            { 85, 76, 10 }, { 67, 39, 10 }, { 54, 37, 10 }, { 46, 0, 5 }, { 55, 71, -7 },
            { 90, 41, 10 }, { 52, 48, 10 }, { 34, 45, 10 }, { 55, 39, 10 }, { 92, 40, 10 },
            { 35, 33, 1 }, { 64, 92, -7 }, { 56, 7, -5 }, { 9, 37, 1 }, { 12, 71, -8 },
            { 48, 19, -4 }, { 42, 1, 3 }, { 78, 98, -6 }, { 49, 15, 9 }, { 87, 70, 10 },
            { 49, 79, -8 }, { 16, 8, 7 }, { 93, 36, 9 }, { 74, 8, -8 }, { 0, 39, 7 }, };
        double maxWeight = 208;
        double minWeight = -152;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 100 vertices and 200 edges
     */
    @Test
    public void testGetMatching14()
    {
        int[][] edges = new int[][] { { 27, 92, -22 }, { 23, 54, -33 }, { 27, 28, 46 },
            { 7, 89, -98 }, { 48, 36, -23 }, { 87, 39, -6 }, { 40, 70, -21 }, { 34, 60, 14 },
            { 1, 31, -69 }, { 82, 46, -74 }, { 72, 9, 93 }, { 49, 59, 87 }, { 74, 54, -29 },
            { 87, 4, 56 }, { 97, 14, 19 }, { 6, 76, 6 }, { 97, 31, -30 }, { 15, 78, -90 },
            { 24, 95, -19 }, { 41, 15, -85 }, { 44, 51, 6 }, { 64, 78, 14 }, { 70, 56, -59 },
            { 82, 87, -24 }, { 84, 72, 12 }, { 35, 3, 51 }, { 63, 87, -22 }, { 50, 10, 52 },
            { 49, 25, 36 }, { 71, 23, -43 }, { 59, 67, 39 }, { 1, 63, 84 }, { 99, 79, 47 },
            { 54, 86, 10 }, { 41, 42, 19 }, { 70, 97, 17 }, { 33, 63, 59 }, { 16, 33, 66 },
            { 73, 78, -87 }, { 94, 34, -30 }, { 43, 36, 98 }, { 76, 93, -5 }, { 24, 40, 56 },
            { 51, 89, 23 }, { 34, 35, 91 }, { 86, 97, -50 }, { 98, 65, 70 }, { 11, 88, -61 },
            { 76, 82, 82 }, { 77, 12, -30 }, { 59, 4, -57 }, { 5, 22, 86 }, { 75, 68, -98 },
            { 26, 41, -52 }, { 7, 38, -40 }, { 65, 62, 63 }, { 16, 93, -34 }, { 50, 32, -49 },
            { 15, 79, 98 }, { 80, 17, 68 }, { 81, 74, 62 }, { 18, 5, -49 }, { 1, 40, -54 },
            { 31, 68, -70 }, { 93, 0, 53 }, { 39, 50, -73 }, { 25, 65, -69 }, { 70, 94, 9 },
            { 44, 6, 16 }, { 38, 75, 92 }, { 20, 90, -15 }, { 15, 90, 79 }, { 6, 94, -18 },
            { 98, 11, 40 }, { 6, 33, 88 }, { 55, 15, 1 }, { 31, 2, 64 }, { 18, 76, -49 },
            { 90, 78, 65 }, { 95, 26, 51 }, { 72, 43, -97 }, { 80, 49, -56 }, { 21, 56, 62 },
            { 13, 63, 17 }, { 46, 25, 76 }, { 92, 72, -32 }, { 34, 63, 15 }, { 33, 87, 92 },
            { 57, 1, 55 }, { 57, 94, 0 }, { 32, 28, -9 }, { 61, 86, -77 }, { 41, 56, 29 },
            { 97, 62, -68 }, { 69, 80, 42 }, { 50, 68, 31 }, { 79, 28, -100 }, { 70, 49, 36 },
            { 98, 29, 41 }, { 85, 6, -45 }, { 83, 38, 62 }, { 45, 55, 51 }, { 64, 60, 85 },
            { 46, 77, 42 }, { 27, 70, 59 }, { 9, 85, 29 }, { 3, 83, -2 }, { 98, 27, -11 },
            { 95, 61, -8 }, { 39, 48, -2 }, { 36, 79, -18 }, { 18, 87, -63 }, { 97, 0, -93 },
            { 61, 87, 59 }, { 29, 72, -90 }, { 93, 83, 53 }, { 17, 84, -58 }, { 49, 39, -24 },
            { 98, 10, -75 }, { 84, 74, -12 }, { 52, 71, 33 }, { 45, 32, -94 }, { 35, 21, -2 },
            { 15, 94, 90 }, { 15, 87, 53 }, { 47, 18, -37 }, { 92, 21, -75 }, { 35, 8, 39 },
            { 57, 52, 65 }, { 25, 87, 65 }, { 92, 26, 99 }, { 51, 23, -81 }, { 83, 28, -71 },
            { 83, 8, -91 }, { 20, 79, 75 }, { 72, 52, -45 }, { 62, 86, -37 }, { 86, 45, -94 },
            { 42, 31, 60 }, { 23, 34, 41 }, { 45, 64, -40 }, { 74, 17, -66 }, { 19, 91, -66 },
            { 71, 27, 31 }, { 76, 33, -16 }, { 56, 47, -22 }, { 6, 15, -5 }, { 95, 8, 49 },
            { 40, 86, 48 }, { 57, 95, 52 }, { 16, 72, -20 }, { 66, 16, 36 }, { 31, 71, 36 },
            { 66, 68, 87 }, { 56, 54, -58 }, { 43, 39, 70 }, { 94, 93, -28 }, { 12, 2, -93 },
            { 47, 38, 60 }, { 17, 22, 31 }, { 8, 34, 1 }, { 47, 14, 92 }, { 91, 79, 76 },
            { 22, 81, 59 }, { 70, 51, 28 }, { 67, 50, 84 }, { 51, 56, -78 }, { 40, 71, -16 },
            { 4, 73, -100 }, { 50, 71, -72 }, { 9, 33, -41 }, { 37, 92, 60 }, { 10, 39, 60 },
            { 49, 12, -3 }, { 27, 85, -78 }, { 81, 19, 92 }, { 18, 72, 97 }, { 60, 67, 95 },
            { 56, 71, 45 }, { 12, 9, -69 }, { 99, 27, 94 }, { 94, 55, 93 }, { 47, 92, 100 },
            { 49, 7, 92 }, { 84, 89, 99 }, { 32, 98, 9 }, { 84, 93, -63 }, { 94, 40, -45 },
            { 32, 68, 9 }, { 28, 86, -81 }, { 88, 59, -39 }, { 25, 29, 27 }, { 81, 88, -56 },
            { 16, 3, 83 }, { 6, 73, 94 }, { 67, 70, -75 }, { 36, 20, 67 }, { 79, 17, 82 },
            { 42, 63, -73 }, { 35, 93, 63 }, };
        double maxWeight = 2748;
        double minWeight = -2402;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 100 vertices and 400 edges
     */
    @Test
    public void testGetMatching15()
    {
        int[][] edges = new int[][] { { 96, 57, 84 }, { 82, 47, 59 }, { 13, 22, -28 },
            { 6, 17, 64 }, { 81, 24, 74 }, { 64, 41, 2 }, { 20, 28, -21 }, { 6, 42, 2 },
            { 47, 75, -79 }, { 99, 28, -39 }, { 41, 92, 51 }, { 29, 8, -11 }, { 1, 19, -2 },
            { 21, 67, -13 }, { 73, 41, 83 }, { 98, 90, -3 }, { 57, 17, -39 }, { 60, 67, 55 },
            { 54, 37, -8 }, { 68, 85, 86 }, { 54, 40, -24 }, { 44, 7, -84 }, { 85, 47, 34 },
            { 57, 64, 56 }, { 75, 23, 63 }, { 71, 2, 25 }, { 92, 34, -31 }, { 30, 96, -26 },
            { 87, 46, -23 }, { 72, 57, -64 }, { 15, 11, -38 }, { 86, 81, 38 }, { 20, 80, 63 },
            { 59, 36, -63 }, { 37, 68, 25 }, { 78, 36, 49 }, { 94, 17, -43 }, { 39, 4, -41 },
            { 41, 14, 44 }, { 11, 68, 9 }, { 94, 84, -24 }, { 3, 41, -10 }, { 0, 50, -1 },
            { 42, 87, 30 }, { 6, 98, -74 }, { 66, 43, 47 }, { 81, 37, -49 }, { 55, 32, 30 },
            { 40, 49, 62 }, { 14, 3, -67 }, { 85, 39, 82 }, { 22, 46, -92 }, { 8, 80, -19 },
            { 83, 41, -97 }, { 87, 50, -36 }, { 37, 6, 65 }, { 98, 63, -90 }, { 39, 47, -30 },
            { 72, 93, 11 }, { 18, 29, -53 }, { 93, 40, -13 }, { 26, 74, -88 }, { 87, 25, 52 },
            { 73, 17, 15 }, { 6, 78, 31 }, { 5, 73, 92 }, { 25, 57, 91 }, { 18, 34, 89 },
            { 21, 60, -2 }, { 94, 43, -74 }, { 96, 27, -56 }, { 62, 37, -81 }, { 77, 57, -2 },
            { 69, 3, -19 }, { 28, 81, -46 }, { 38, 95, -52 }, { 0, 97, -58 }, { 87, 55, -22 },
            { 22, 90, 76 }, { 30, 56, 56 }, { 17, 90, -68 }, { 33, 76, -78 }, { 28, 90, -94 },
            { 42, 88, -26 }, { 11, 34, -31 }, { 87, 78, 80 }, { 89, 60, 78 }, { 14, 67, -33 },
            { 47, 74, 9 }, { 30, 38, -2 }, { 22, 12, -51 }, { 80, 85, -2 }, { 8, 1, -91 },
            { 2, 90, 89 }, { 43, 59, -40 }, { 69, 52, 81 }, { 30, 69, 65 }, { 28, 71, -91 },
            { 72, 64, 97 }, { 84, 33, -17 }, { 38, 41, 65 }, { 74, 30, -52 }, { 72, 49, 1 },
            { 24, 97, -64 }, { 63, 66, -50 }, { 21, 9, -76 }, { 45, 10, -92 }, { 12, 88, -52 },
            { 54, 48, 53 }, { 95, 42, -85 }, { 40, 46, -24 }, { 42, 12, -20 }, { 91, 30, -73 },
            { 74, 22, 3 }, { 29, 96, -60 }, { 17, 2, -30 }, { 70, 60, -12 }, { 55, 24, 25 },
            { 3, 53, 7 }, { 41, 71, 71 }, { 5, 11, 36 }, { 4, 82, -71 }, { 88, 63, -99 },
            { 77, 78, 10 }, { 1, 32, 26 }, { 35, 11, 16 }, { 0, 73, -85 }, { 73, 37, 74 },
            { 97, 6, 61 }, { 85, 21, -73 }, { 57, 20, -44 }, { 33, 39, -71 }, { 9, 8, -81 },
            { 21, 65, -47 }, { 90, 18, 97 }, { 37, 25, -64 }, { 95, 94, -74 }, { 37, 80, 83 },
            { 59, 79, 50 }, { 42, 91, -14 }, { 14, 54, 32 }, { 41, 34, 60 }, { 17, 26, -91 },
            { 40, 90, -48 }, { 86, 31, 72 }, { 80, 35, -20 }, { 81, 6, -31 }, { 77, 91, -84 },
            { 55, 68, 36 }, { 99, 69, 74 }, { 88, 92, -27 }, { 84, 69, 64 }, { 79, 97, 96 },
            { 36, 55, 55 }, { 23, 47, -94 }, { 35, 68, -100 }, { 76, 43, 96 }, { 59, 49, 93 },
            { 52, 61, 0 }, { 66, 51, -79 }, { 47, 73, 21 }, { 82, 98, -12 }, { 69, 89, 71 },
            { 47, 97, -85 }, { 31, 46, -11 }, { 8, 5, 100 }, { 9, 72, 9 }, { 13, 89, 8 },
            { 50, 79, -8 }, { 8, 6, 65 }, { 20, 34, 1 }, { 3, 32, -70 }, { 65, 63, 12 },
            { 21, 61, 83 }, { 98, 56, 1 }, { 44, 60, -54 }, { 6, 16, 83 }, { 18, 56, -84 },
            { 50, 39, 44 }, { 78, 57, -10 }, { 56, 89, 98 }, { 70, 83, 50 }, { 10, 14, 43 },
            { 35, 52, 38 }, { 63, 9, 6 }, { 6, 33, 31 }, { 24, 79, -32 }, { 14, 16, -48 },
            { 60, 6, -6 }, { 85, 25, 20 }, { 94, 66, -76 }, { 59, 78, -67 }, { 45, 78, 24 },
            { 19, 39, 6 }, { 84, 40, 73 }, { 27, 78, -38 }, { 36, 50, -13 }, { 10, 19, 59 },
            { 87, 47, 86 }, { 77, 94, -68 }, { 92, 64, -22 }, { 88, 16, -33 }, { 22, 19, 46 },
            { 17, 77, -98 }, { 91, 47, -23 }, { 56, 25, -6 }, { 64, 61, -21 }, { 23, 59, 14 },
            { 20, 7, -69 }, { 63, 26, -74 }, { 74, 70, 93 }, { 32, 79, 87 }, { 43, 79, -29 },
            { 11, 29, 56 }, { 48, 27, 19 }, { 25, 58, 6 }, { 69, 92, -30 }, { 45, 73, -90 },
            { 65, 26, -19 }, { 53, 32, -85 }, { 7, 80, 6 }, { 16, 84, 14 }, { 6, 22, -59 },
            { 0, 30, -24 }, { 52, 71, 12 }, { 84, 30, 51 }, { 17, 99, -22 }, { 36, 75, 52 },
            { 49, 29, 36 }, { 92, 7, -43 }, { 53, 70, 39 }, { 96, 62, 84 }, { 72, 60, 47 },
            { 83, 24, 10 }, { 22, 26, 19 }, { 2, 55, 17 }, { 3, 66, 59 }, { 56, 64, 66 },
            { 8, 68, -87 }, { 3, 12, -30 }, { 45, 7, 98 }, { 53, 90, -5 }, { 6, 73, 56 },
            { 32, 10, 23 }, { 7, 19, 91 }, { 40, 44, -50 }, { 53, 23, 70 }, { 82, 10, -61 },
            { 86, 36, 82 }, { 59, 67, -30 }, { 35, 40, -57 }, { 29, 1, 86 }, { 46, 96, -98 },
            { 2, 21, -52 }, { 28, 41, -40 }, { 98, 48, 63 }, { 75, 67, -34 }, { 25, 91, -49 },
            { 28, 30, 98 }, { 14, 5, 68 }, { 71, 9, 62 }, { 27, 70, -49 }, { 72, 42, -54 },
            { 19, 69, -70 }, { 25, 86, 53 }, { 34, 33, -73 }, { 4, 36, -69 }, { 52, 48, 9 },
            { 92, 40, 16 }, { 76, 29, 92 }, { 55, 21, -15 }, { 86, 16, 79 }, { 50, 30, -18 },
            { 70, 79, 40 }, { 36, 74, 88 }, { 86, 39, 1 }, { 95, 10, 64 }, { 27, 94, -49 },
            { 44, 0, 65 }, { 88, 3, 51 }, { 53, 85, -97 }, { 81, 70, -56 }, { 8, 19, 62 },
            { 4, 7, 17 }, { 95, 68, 76 }, { 79, 99, -32 }, { 41, 13, 15 }, { 86, 3, 92 },
            { 19, 87, 55 }, { 4, 92, 0 }, { 46, 94, -9 }, { 59, 58, -77 }, { 75, 13, 29 },
            { 20, 19, -68 }, { 94, 1, 42 }, { 47, 64, 31 }, { 58, 40, -100 }, { 22, 42, 36 },
            { 59, 37, 41 }, { 38, 82, -45 }, { 21, 32, 62 }, { 95, 61, 51 }, { 22, 70, 85 },
            { 39, 21, 42 }, { 99, 20, 59 }, { 75, 51, 29 }, { 67, 93, -2 }, { 91, 5, -11 },
            { 27, 72, -8 }, { 75, 12, -2 }, { 44, 31, -18 }, { 89, 5, -63 }, { 46, 50, -93 },
            { 48, 93, 59 }, { 41, 60, -90 }, { 93, 80, 53 }, { 85, 15, -58 }, { 73, 27, -24 },
            { 7, 65, -75 }, { 12, 84, -12 }, { 78, 33, 33 }, { 68, 49, -94 }, { 11, 32, -2 },
            { 0, 10, 90 }, { 81, 10, 53 }, { 77, 92, -37 }, { 99, 91, -75 }, { 74, 60, 39 },
            { 78, 49, 65 }, { 4, 96, 65 }, { 1, 25, 99 }, { 93, 36, -81 }, { 27, 17, -71 },
            { 27, 59, -91 }, { 53, 55, 75 }, { 2, 36, -45 }, { 49, 96, -37 }, { 14, 35, -94 },
            { 98, 27, 60 }, { 9, 15, 41 }, { 36, 34, -40 }, { 75, 18, -66 }, { 90, 88, -66 },
            { 48, 63, 31 }, { 6, 57, -16 }, { 2, 95, -22 }, { 61, 15, -5 }, { 17, 55, 49 },
            { 59, 14, 48 }, { 3, 25, 52 }, { 48, 26, -20 }, { 63, 97, 36 }, { 24, 47, 36 },
            { 5, 41, 87 }, { 52, 49, -58 }, { 18, 91, 70 }, { 82, 57, -28 }, { 81, 94, -93 },
            { 90, 91, 60 }, { 69, 15, 31 }, { 34, 69, 1 }, { 81, 47, 92 }, { 11, 24, 76 },
            { 54, 78, 59 }, { 76, 57, 28 }, { 11, 41, 84 }, { 44, 54, -78 }, { 26, 14, -16 },
            { 67, 34, -100 }, { 93, 51, -72 }, { 96, 26, -41 }, { 7, 10, 60 }, { 57, 66, 60 },
            { 33, 44, -3 }, { 3, 87, -78 }, { 41, 53, 92 }, { 85, 86, 97 }, { 73, 54, 95 },
            { 6, 43, 45 }, { 64, 70, -69 }, { 22, 67, 94 }, { 32, 76, 93 }, { 0, 9, 100 },
            { 61, 14, 92 }, { 95, 62, 99 }, { 96, 48, 9 }, { 65, 44, -63 }, { 23, 90, -45 },
            { 1, 40, 9 }, { 73, 89, -81 }, { 42, 39, -39 }, { 5, 51, 27 }, { 10, 41, -56 },
            { 68, 0, 83 }, { 19, 52, 94 }, { 57, 55, -75 }, { 68, 19, 67 }, { 10, 84, 82 },
            { 68, 62, -73 }, { 12, 51, 63 }, };
        double maxWeight = 3267;
        double minWeight = -3239;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 200 vertices and 500 edges
     */
    @Test
    public void testGetMatching16()
    {
        int[][] edges = new int[][] { { 120, 6, -58 }, { 133, 125, -8 }, { 32, 184, 94 },
            { 160, 198, -53 }, { 89, 168, -44 }, { 104, 138, 16 }, { 194, 195, -31 },
            { 26, 49, -2 }, { 24, 175, -80 }, { 144, 14, 46 }, { 141, 105, -51 }, { 44, 23, 86 },
            { 191, 87, -47 }, { 161, 148, -95 }, { 109, 64, 53 }, { 158, 133, 61 },
            { 176, 161, -64 }, { 3, 40, -48 }, { 174, 98, 99 }, { 193, 74, -83 }, { 164, 113, -78 },
            { 13, 4, 2 }, { 157, 102, 57 }, { 85, 168, -15 }, { 94, 112, -16 }, { 182, 181, -36 },
            { 188, 94, 31 }, { 172, 168, -41 }, { 152, 129, -35 }, { 123, 124, -77 },
            { 105, 41, 67 }, { 78, 157, -56 }, { 114, 101, -67 }, { 190, 16, 42 }, { 141, 40, 60 },
            { 165, 37, 21 }, { 176, 106, -92 }, { 171, 169, -48 }, { 87, 195, -10 },
            { 144, 125, 19 }, { 114, 166, -74 }, { 139, 4, -18 }, { 33, 28, -68 }, { 82, 172, -49 },
            { 45, 198, 42 }, { 163, 19, -78 }, { 88, 80, 36 }, { 2, 142, -12 }, { 199, 43, -29 },
            { 20, 12, 96 }, { 78, 179, 46 }, { 124, 120, 81 }, { 52, 97, 17 }, { 99, 112, -63 },
            { 33, 2, 27 }, { 148, 64, -14 }, { 157, 137, 29 }, { 137, 163, 85 }, { 171, 1, -82 },
            { 191, 196, -38 }, { 54, 14, -5 }, { 145, 81, -13 }, { 138, 149, 60 }, { 28, 40, -55 },
            { 174, 34, -52 }, { 143, 61, -66 }, { 159, 169, -71 }, { 53, 179, -55 }, { 0, 40, -12 },
            { 137, 3, -61 }, { 177, 16, 78 }, { 166, 57, 69 }, { 182, 12, -61 }, { 186, 190, -54 },
            { 52, 192, 80 }, { 11, 129, -6 }, { 85, 5, -97 }, { 95, 136, -40 }, { 155, 132, 8 },
            { 191, 121, -59 }, { 157, 138, -5 }, { 154, 148, 17 }, { 106, 61, 56 }, { 141, 53, 25 },
            { 177, 166, -22 }, { 106, 159, 10 }, { 15, 38, -97 }, { 6, 22, 76 }, { 67, 44, -52 },
            { 31, 60, 88 }, { 118, 167, 99 }, { 189, 127, -30 }, { 151, 23, 90 }, { 96, 178, 7 },
            { 150, 186, -60 }, { 82, 186, 63 }, { 15, 124, -72 }, { 159, 98, -24 }, { 41, 135, 9 },
            { 2, 154, 29 }, { 198, 77, 84 }, { 169, 12, 59 }, { 150, 177, -28 }, { 76, 96, 64 },
            { 7, 62, 74 }, { 184, 121, 2 }, { 75, 25, -21 }, { 134, 144, 2 }, { 4, 89, -79 },
            { 86, 161, -39 }, { 192, 140, 51 }, { 60, 107, -11 }, { 196, 157, -2 }, { 51, 96, -13 },
            { 127, 126, 83 }, { 192, 187, -3 }, { 37, 106, -39 }, { 128, 72, 55 }, { 36, 39, -8 },
            { 144, 151, 86 }, { 177, 143, -24 }, { 133, 37, -84 }, { 76, 16, 34 }, { 43, 102, 56 },
            { 171, 105, 63 }, { 40, 127, 25 }, { 150, 182, -31 }, { 155, 35, -26 }, { 32, 65, -23 },
            { 69, 81, -64 }, { 103, 122, -38 }, { 126, 93, 38 }, { 38, 185, 63 }, { 154, 12, -63 },
            { 104, 194, 25 }, { 85, 173, 49 }, { 128, 81, -43 }, { 140, 12, -41 }, { 71, 126, 44 },
            { 134, 170, 9 }, { 117, 196, -24 }, { 27, 91, -10 }, { 163, 86, -1 }, { 83, 70, 30 },
            { 184, 113, -74 }, { 42, 1, 47 }, { 59, 152, -49 }, { 15, 101, 30 }, { 27, 141, 62 },
            { 21, 181, -67 }, { 167, 171, 82 }, { 38, 6, -92 }, { 47, 31, -19 }, { 168, 171, -97 },
            { 92, 19, -36 }, { 171, 96, 65 }, { 96, 8, -90 }, { 68, 162, -30 }, { 21, 173, 11 },
            { 10, 145, -53 }, { 41, 36, -13 }, { 79, 2, -88 }, { 0, 70, 52 }, { 33, 63, 15 },
            { 162, 20, 31 }, { 9, 32, 92 }, { 78, 184, 91 }, { 147, 47, 89 }, { 22, 4, -2 },
            { 102, 87, -74 }, { 125, 67, -56 }, { 119, 93, -81 }, { 103, 118, -2 },
            { 49, 163, -19 }, { 151, 81, -46 }, { 167, 60, -52 }, { 157, 133, -58 },
            { 92, 134, -22 }, { 196, 6, 76 }, { 23, 103, 56 }, { 148, 84, -68 }, { 170, 166, -78 },
            { 127, 155, -94 }, { 74, 45, -26 }, { 163, 153, -31 }, { 106, 73, 80 }, { 47, 68, 78 },
            { 16, 29, -33 }, { 114, 176, 9 }, { 108, 119, -2 }, { 79, 136, -51 }, { 6, 51, -2 },
            { 142, 76, -91 }, { 167, 15, 89 }, { 175, 187, -40 }, { 147, 16, 81 }, { 40, 17, 65 },
            { 124, 20, -91 }, { 89, 107, 97 }, { 58, 97, -17 }, { 125, 17, 65 }, { 98, 148, -52 },
            { 12, 156, 1 }, { 180, 13, -64 }, { 150, 138, -50 }, { 82, 2, -76 }, { 10, 183, -92 },
            { 133, 121, -52 }, { 152, 84, 53 }, { 89, 99, -85 }, { 148, 21, -24 }, { 21, 46, -20 },
            { 99, 182, -73 }, { 179, 98, 3 }, { 82, 102, -60 }, { 174, 167, -30 }, { 13, 72, -12 },
            { 197, 22, 25 }, { 110, 87, 7 }, { 50, 142, 71 }, { 175, 152, 36 }, { 184, 33, -71 },
            { 192, 149, -99 }, { 5, 110, 10 }, { 156, 120, 26 }, { 51, 153, 16 }, { 25, 181, -85 },
            { 37, 81, 74 }, { 135, 140, 61 }, { 40, 136, -73 }, { 155, 133, -44 }, { 199, 33, -71 },
            { 11, 86, -81 }, { 124, 134, -47 }, { 68, 106, 97 }, { 131, 152, -64 }, { 83, 67, -74 },
            { 1, 4, 83 }, { 9, 155, 50 }, { 20, 27, -14 }, { 146, 118, 32 }, { 37, 129, 60 },
            { 55, 162, -91 }, { 139, 8, -48 }, { 2, 122, 72 }, { 2, 15, -20 }, { 194, 48, -31 },
            { 156, 102, -84 }, { 119, 130, 36 }, { 29, 44, 74 }, { 56, 127, -27 }, { 165, 116, 64 },
            { 59, 3, 96 }, { 138, 155, 55 }, { 148, 176, -94 }, { 124, 78, -100 }, { 66, 158, 96 },
            { 29, 91, 93 }, { 190, 53, 0 }, { 144, 13, -79 }, { 13, 73, 21 }, { 25, 69, -12 },
            { 55, 150, 71 }, { 13, 78, -85 }, { 57, 117, -11 }, { 91, 160, 100 }, { 40, 46, 9 },
            { 146, 64, 8 }, { 110, 119, -8 }, { 173, 78, 65 }, { 170, 181, 1 }, { 109, 136, -70 },
            { 179, 121, 12 }, { 69, 87, 83 }, { 117, 30, 1 }, { 115, 79, -54 }, { 31, 104, 83 },
            { 61, 11, -84 }, { 100, 104, 44 }, { 114, 33, -10 }, { 32, 70, 98 }, { 83, 2, 50 },
            { 197, 55, 43 }, { 42, 102, 38 }, { 158, 120, 6 }, { 137, 46, 31 }, { 35, 161, -32 },
            { 173, 138, -48 }, { 102, 167, -6 }, { 60, 149, 20 }, { 62, 28, -76 },
            { 197, 158, -67 }, { 178, 40, 24 }, { 159, 73, 6 }, { 23, 29, 73 }, { 84, 39, -38 },
            { 37, 182, -13 }, { 71, 10, 59 }, { 167, 64, 86 }, { 35, 124, -68 }, { 49, 13, -22 },
            { 94, 145, -33 }, { 7, 165, 46 }, { 30, 123, -98 }, { 107, 127, -23 }, { 35, 189, -6 },
            { 183, 39, -21 }, { 5, 98, 14 }, { 52, 177, -69 }, { 62, 0, -74 }, { 26, 70, 93 },
            { 58, 32, 87 }, { 152, 189, -29 }, { 86, 104, 56 }, { 198, 180, 19 }, { 15, 100, 6 },
            { 113, 183, -30 }, { 101, 80, -90 }, { 54, 33, -19 }, { 40, 90, -85 }, { 114, 74, 6 },
            { 152, 103, 14 }, { 107, 115, -59 }, { 182, 50, -24 }, { 42, 54, 12 }, { 75, 26, 51 },
            { 149, 148, -22 }, { 177, 2, 52 }, { 184, 188, 36 }, { 169, 97, -43 }, { 22, 124, 39 },
            { 100, 85, 84 }, { 77, 36, 47 }, { 79, 92, 10 }, { 33, 177, 19 }, { 35, 87, 17 },
            { 101, 67, 59 }, { 188, 160, 66 }, { 143, 154, -87 }, { 8, 172, -30 }, { 164, 45, 98 },
            { 42, 26, -5 }, { 148, 19, 56 }, { 32, 101, 23 }, { 86, 47, 91 }, { 1, 0, -50 },
            { 134, 62, 70 }, { 147, 152, -61 }, { 166, 116, 82 }, { 123, 199, -30 },
            { 27, 15, -57 }, { 198, 87, 86 }, { 98, 10, -98 }, { 8, 4, -52 }, { 170, 29, -40 },
            { 130, 158, 63 }, { 155, 131, -34 }, { 105, 182, -49 }, { 191, 182, 98 },
            { 20, 47, 68 }, { 71, 79, 62 }, { 150, 32, -49 }, { 81, 9, -54 }, { 77, 56, -70 },
            { 113, 103, 53 }, { 131, 97, -73 }, { 13, 139, -69 }, { 18, 1, 9 }, { 53, 170, 16 },
            { 148, 38, 92 }, { 19, 85, -15 }, { 27, 137, 79 }, { 71, 58, -18 }, { 175, 37, 40 },
            { 94, 99, 88 }, { 70, 104, 1 }, { 148, 37, 64 }, { 72, 25, -49 }, { 198, 125, 65 },
            { 68, 108, 51 }, { 85, 63, -97 }, { 180, 187, -56 }, { 128, 47, 62 }, { 64, 198, 17 },
            { 41, 140, 76 }, { 18, 5, -32 }, { 98, 99, 15 }, { 173, 140, 92 }, { 97, 145, 55 },
            { 99, 151, 0 }, { 114, 35, -9 }, { 126, 175, -77 }, { 51, 154, 29 }, { 31, 173, -68 },
            { 70, 170, 42 }, { 14, 61, 31 }, { 114, 11, -100 }, { 89, 197, 36 }, { 19, 2, 41 },
            { 160, 54, -45 }, { 59, 161, 62 }, { 96, 74, 51 }, { 0, 13, 85 }, { 22, 72, 42 },
            { 176, 135, 59 }, { 94, 150, 29 }, { 122, 23, -2 }, { 20, 109, -11 }, { 14, 140, -8 },
            { 91, 153, -2 }, { 24, 104, -18 }, { 132, 42, -63 }, { 193, 178, -93 },
            { 177, 142, 59 }, { 46, 68, -90 }, { 114, 184, 53 }, { 4, 120, -58 }, { 167, 141, -24 },
            { 188, 37, -75 }, { 183, 117, -12 }, { 116, 14, 33 }, { 184, 7, -94 }, { 134, 21, -2 },
            { 104, 89, 90 }, { 51, 8, 53 }, { 164, 151, -37 }, { 158, 20, -75 }, { 8, 78, 39 },
            { 131, 62, 65 }, { 113, 5, 65 }, { 86, 13, 99 }, { 133, 56, -81 }, { 183, 53, -71 },
            { 142, 145, -91 }, { 152, 194, 75 }, { 117, 189, -45 }, { 25, 29, -37 },
            { 143, 95, -94 }, { 50, 180, 60 }, { 150, 132, 41 }, { 16, 96, -40 }, { 42, 135, -66 },
            { 148, 34, -66 }, { 10, 6, 31 }, { 112, 22, -16 }, { 5, 77, -22 }, { 91, 4, -5 },
            { 166, 155, 49 }, { 31, 155, 48 }, { 183, 75, 52 }, { 112, 31, -20 }, { 44, 12, 36 },
            { 144, 6, 36 }, { 20, 36, 87 }, { 81, 46, -58 }, { 27, 8, 70 }, { 162, 73, -28 },
            { 187, 112, -93 }, { 109, 101, 60 }, { 108, 138, 31 }, { 16, 78, 1 }, { 145, 141, 92 },
            { 98, 30, 76 }, { 45, 120, 59 }, { 41, 174, 28 }, { 14, 2, 84 }, { 97, 166, -78 },
            { 120, 51, -16 }, { 39, 90, -100 }, { 149, 35, -72 }, { 142, 198, -41 },
            { 35, 171, 60 }, { 65, 148, 60 }, { 38, 2, -3 }, { 139, 44, -78 }, { 72, 170, 92 },
            { 75, 173, 97 }, { 110, 91, 95 }, { 27, 34, 45 }, { 116, 134, -69 }, { 171, 103, 94 },
            { 147, 93, 93 }, { 97, 140, 100 }, { 130, 58, 92 }, { 76, 154, 99 }, { 91, 54, 9 },
            { 97, 117, -63 }, { 183, 12, -45 }, { 37, 89, 9 }, { 148, 62, -81 }, { 116, 192, -39 },
            { 5, 142, 27 }, { 56, 44, -56 }, { 178, 16, 83 }, { 54, 137, 94 }, { 178, 199, -75 },
            { 71, 22, 67 }, { 185, 4, 82 }, { 57, 65, -73 }, { 160, 30, 63 }, };
        double maxWeight = 5229;
        double minWeight = -5301;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 400 vertices and 1000 edges
     */
    @Test
    public void testGetMatching17()
    {
        int[][] edges = new int[][] { { 226, 265, -38 }, { 346, 351, 23 }, { 247, 266, -32 },
            { 296, 345, -49 }, { 204, 302, -87 }, { 12, 363, 67 }, { 48, 148, -98 },
            { 135, 190, 69 }, { 99, 98, -13 }, { 248, 298, -17 }, { 395, 124, -59 },
            { 150, 202, 33 }, { 282, 55, -87 }, { 265, 111, -30 }, { 127, 158, 42 },
            { 207, 329, 54 }, { 187, 180, 33 }, { 44, 146, 33 }, { 310, 268, 7 }, { 306, 349, -8 },
            { 241, 5, 95 }, { 243, 304, -10 }, { 206, 298, -76 }, { 307, 334, 22 },
            { 221, 24, -78 }, { 370, 199, -77 }, { 57, 289, -35 }, { 72, 20, -53 }, { 51, 144, 30 },
            { 83, 221, 42 }, { 255, 334, 18 }, { 62, 301, -59 }, { 76, 148, -95 }, { 323, 312, 89 },
            { 168, 18, 56 }, { 3, 123, 27 }, { 21, 95, -99 }, { 36, 229, 36 }, { 309, 225, 87 },
            { 331, 4, 30 }, { 188, 16, 90 }, { 299, 67, 29 }, { 23, 101, 80 }, { 30, 19, -15 },
            { 344, 73, 97 }, { 130, 55, 9 }, { 276, 363, 83 }, { 55, 340, 37 }, { 207, 209, 85 },
            { 374, 104, 15 }, { 39, 339, -83 }, { 372, 154, -82 }, { 127, 100, 19 },
            { 344, 291, -43 }, { 366, 178, 77 }, { 74, 59, -63 }, { 393, 64, -98 },
            { 222, 198, 53 }, { 364, 18, 72 }, { 368, 399, -46 }, { 207, 104, 61 }, { 1, 390, 84 },
            { 7, 174, -34 }, { 225, 135, -52 }, { 123, 275, 51 }, { 238, 155, 48 }, { 90, 248, 9 },
            { 188, 290, -62 }, { 105, 156, -43 }, { 23, 352, 22 }, { 34, 165, 45 },
            { 86, 312, -32 }, { 394, 33, 8 }, { 193, 326, -70 }, { 274, 174, -57 },
            { 293, 257, -5 }, { 353, 374, -19 }, { 53, 81, 45 }, { 145, 383, -3 }, { 37, 333, -65 },
            { 264, 162, 62 }, { 290, 8, -93 }, { 233, 41, -51 }, { 84, 140, -6 }, { 170, 30, -57 },
            { 8, 327, 57 }, { 151, 210, -39 }, { 376, 212, -36 }, { 216, 123, 95 }, { 44, 205, 54 },
            { 256, 66, -11 }, { 198, 49, -8 }, { 295, 219, -100 }, { 361, 224, -15 },
            { 137, 390, -6 }, { 378, 142, -8 }, { 174, 53, -46 }, { 347, 151, -100 },
            { 331, 206, 31 }, { 52, 175, 84 }, { 266, 196, 97 }, { 371, 365, -23 }, { 7, 193, 43 },
            { 279, 264, 21 }, { 220, 102, -54 }, { 344, 163, -99 }, { 30, 38, 2 }, { 170, 325, 35 },
            { 312, 47, -10 }, { 99, 332, 56 }, { 246, 218, -55 }, { 329, 3, -31 }, { 325, 69, 58 },
            { 0, 320, 69 }, { 330, 15, -39 }, { 371, 227, 34 }, { 338, 196, 84 }, { 169, 41, -55 },
            { 252, 172, 87 }, { 93, 10, -49 }, { 109, 302, 81 }, { 68, 353, -87 }, { 218, 199, -2 },
            { 379, 169, 39 }, { 219, 124, 23 }, { 82, 308, 35 }, { 26, 179, -89 },
            { 389, 202, -42 }, { 218, 92, -5 }, { 157, 260, 35 }, { 346, 288, -17 },
            { 360, 375, -52 }, { 298, 315, 45 }, { 325, 243, 92 }, { 110, 262, -47 },
            { 290, 254, 28 }, { 386, 344, 52 }, { 186, 269, 89 }, { 109, 110, 94 }, { 74, 67, 4 },
            { 346, 168, -76 }, { 372, 221, 75 }, { 196, 230, -82 }, { 7, 44, -9 },
            { 336, 226, -74 }, { 124, 84, 5 }, { 240, 15, -3 }, { 277, 116, -12 },
            { 214, 290, -48 }, { 242, 135, -44 }, { 294, 128, 5 }, { 101, 315, -70 },
            { 272, 185, -87 }, { 88, 352, -47 }, { 268, 163, -87 }, { 204, 355, -82 },
            { 280, 41, 40 }, { 292, 171, -15 }, { 223, 212, -8 }, { 113, 259, 56 },
            { 203, 155, -85 }, { 288, 88, 22 }, { 174, 391, 36 }, { 161, 37, -79 },
            { 140, 298, 37 }, { 170, 141, -35 }, { 331, 321, 50 }, { 77, 41, 6 }, { 366, 295, -34 },
            { 22, 195, 94 }, { 175, 220, -51 }, { 377, 354, 44 }, { 92, 166, 45 }, { 233, 358, 64 },
            { 148, 310, 3 }, { 44, 246, -19 }, { 275, 157, 99 }, { 223, 56, 31 }, { 187, 193, 26 },
            { 21, 160, 6 }, { 356, 314, -35 }, { 308, 205, -36 }, { 310, 290, -41 },
            { 338, 48, -87 }, { 277, 28, 6 }, { 220, 78, -94 }, { 237, 275, 27 }, { 264, 88, 28 },
            { 31, 343, -86 }, { 237, 104, 40 }, { 139, 67, 27 }, { 337, 78, 39 }, { 175, 194, 50 },
            { 354, 60, -6 }, { 384, 228, 95 }, { 327, 111, 20 }, { 279, 362, 56 }, { 40, 190, -82 },
            { 207, 10, -21 }, { 268, 328, -15 }, { 284, 15, -14 }, { 67, 265, -65 }, { 15, 80, -2 },
            { 339, 316, -68 }, { 184, 52, -2 }, { 359, 247, -38 }, { 284, 324, 54 },
            { 390, 291, -15 }, { 376, 98, -91 }, { 353, 155, -96 }, { 388, 296, 17 },
            { 353, 248, 19 }, { 301, 243, 32 }, { 125, 385, -48 }, { 51, 168, -35 },
            { 44, 297, 64 }, { 321, 171, -35 }, { 396, 250, 76 }, { 305, 136, 70 },
            { 112, 150, 82 }, { 272, 316, -25 }, { 29, 80, -79 }, { 5, 397, 82 }, { 85, 19, 17 },
            { 341, 255, -60 }, { 49, 293, -31 }, { 233, 3, 55 }, { 317, 172, 46 }, { 382, 247, 80 },
            { 335, 297, 97 }, { 221, 160, 6 }, { 399, 301, 65 }, { 93, 361, 100 },
            { 299, 210, -47 }, { 351, 4, -5 }, { 94, 191, 24 }, { 313, 367, -85 },
            { 244, 340, -42 }, { 319, 47, 31 }, { 388, 222, -50 }, { 204, 276, 50 },
            { 73, 346, 17 }, { 304, 269, -97 }, { 337, 110, -23 }, { 314, 253, -4 },
            { 104, 115, -55 }, { 150, 303, -53 }, { 294, 216, 18 }, { 137, 85, 42 },
            { 23, 211, -76 }, { 44, 295, 76 }, { 362, 136, -4 }, { 230, 73, 46 }, { 109, 303, -14 },
            { 269, 222, 19 }, { 216, 241, -62 }, { 351, 364, -66 }, { 103, 212, -25 },
            { 205, 207, -54 }, { 365, 214, 29 }, { 9, 194, -50 }, { 102, 286, 71 },
            { 176, 267, -33 }, { 284, 321, -69 }, { 57, 55, 0 }, { 110, 275, 97 }, { 207, 213, 6 },
            { 396, 239, -8 }, { 365, 119, 27 }, { 327, 40, -26 }, { 232, 54, -9 }, { 55, 48, -62 },
            { 210, 37, -99 }, { 61, 8, 34 }, { 109, 265, -82 }, { 27, 89, 77 }, { 269, 55, -74 },
            { 178, 114, 12 }, { 50, 142, -88 }, { 27, 115, -94 }, { 133, 230, 48 },
            { 360, 345, -66 }, { 97, 297, 35 }, { 29, 171, 100 }, { 229, 384, 77 }, { 26, 69, -75 },
            { 280, 241, -38 }, { 27, 99, -65 }, { 60, 136, -63 }, { 178, 79, 33 }, { 375, 67, 65 },
            { 132, 317, 40 }, { 383, 242, -52 }, { 274, 375, 8 }, { 165, 223, 48 },
            { 266, 149, 33 }, { 372, 234, -76 }, { 142, 367, 40 }, { 314, 392, -38 },
            { 211, 326, -40 }, { 86, 44, 11 }, { 269, 319, 97 }, { 292, 86, 13 }, { 362, 305, -17 },
            { 102, 396, -74 }, { 308, 118, 89 }, { 230, 397, 20 }, { 335, 276, 10 },
            { 352, 390, 13 }, { 224, 158, -16 }, { 270, 284, 95 }, { 182, 187, -46 },
            { 129, 92, -67 }, { 7, 182, 48 }, { 330, 68, 90 }, { 282, 381, -90 }, { 389, 238, -22 },
            { 142, 195, 84 }, { 296, 217, 76 }, { 249, 197, 91 }, { 348, 265, 23 }, { 18, 59, -32 },
            { 379, 288, -59 }, { 338, 130, -2 }, { 252, 332, 73 }, { 375, 231, -61 },
            { 285, 322, -61 }, { 313, 358, -26 }, { 255, 332, -1 }, { 66, 4, -79 },
            { 39, 255, -66 }, { 392, 89, -67 }, { 194, 224, -42 }, { 334, 385, 97 },
            { 89, 391, 64 }, { 363, 149, -97 }, { 278, 68, -28 }, { 393, 37, -14 },
            { 390, 241, 65 }, { 257, 89, -42 }, { 113, 280, 3 }, { 374, 312, 26 },
            { 390, 359, -64 }, { 64, 168, 32 }, { 44, 96, 24 }, { 283, 343, -17 }, { 53, 229, 82 },
            { 255, 9, 5 }, { 180, 84, 72 }, { 114, 211, -20 }, { 257, 239, -45 }, { 156, 279, -88 },
            { 123, 31, -21 }, { 170, 129, 61 }, { 46, 282, -62 }, { 102, 305, 67 }, { 22, 146, 24 },
            { 357, 329, -22 }, { 260, 160, 43 }, { 130, 41, -66 }, { 190, 177, -85 },
            { 137, 105, -74 }, { 301, 47, 82 }, { 295, 247, -84 }, { 146, 129, 1 }, { 297, 8, 65 },
            { 356, 148, -51 }, { 178, 3, -14 }, { 300, 150, -13 }, { 188, 163, -9 },
            { 375, 97, -5 }, { 307, 387, 60 }, { 380, 98, 29 }, { 317, 23, 30 }, { 102, 337, -72 },
            { 128, 214, 95 }, { 358, 48, 88 }, { 102, 324, 4 }, { 137, 377, -16 }, { 389, 339, 32 },
            { 374, 115, -61 }, { 265, 43, -70 }, { 123, 84, 41 }, { 116, 279, 45 },
            { 153, 366, -54 }, { 183, 226, 64 }, { 286, 163, -87 }, { 243, 154, 64 },
            { 345, 371, -42 }, { 310, 119, -81 }, { 168, 87, 34 }, { 121, 149, 4 },
            { 170, 268, 87 }, { 299, 39, -86 }, { 20, 270, 75 }, { 390, 128, -92 }, { 104, 383, 7 },
            { 249, 319, 37 }, { 280, 367, 91 }, { 152, 17, -89 }, { 370, 93, -37 }, { 56, 375, -6 },
            { 130, 186, -36 }, { 353, 125, 0 }, { 377, 388, 50 }, { 223, 60, 43 },
            { 186, 240, -54 }, { 334, 288, 96 }, { 102, 251, 93 }, { 72, 11, -67 },
            { 138, 353, -38 }, { 287, 92, -2 }, { 327, 189, 19 }, { 231, 208, -95 }, { 49, 225, 0 },
            { 375, 71, 78 }, { 331, 88, -34 }, { 16, 59, -52 }, { 209, 235, -51 },
            { 173, 395, -64 }, { 359, 16, 3 }, { 284, 238, 15 }, { 161, 105, -2 }, { 188, 215, 61 },
            { 35, 27, 22 }, { 249, 259, 72 }, { 42, 222, -6 }, { 37, 266, 24 }, { 43, 165, 87 },
            { 152, 373, 22 }, { 108, 302, -47 }, { 123, 285, 81 }, { 337, 316, -20 },
            { 304, 388, -4 }, { 296, 194, -49 }, { 324, 328, 0 }, { 247, 307, 38 },
            { 248, 372, 49 }, { 102, 280, -15 }, { 316, 377, -94 }, { 248, 257, 3 },
            { 30, 157, -61 }, { 142, 159, -87 }, { 275, 162, 40 }, { 223, 288, 44 },
            { 117, 299, -33 }, { 289, 45, -29 }, { 188, 250, 79 }, { 124, 49, -23 },
            { 320, 381, 81 }, { 255, 282, -81 }, { 254, 57, 43 }, { 195, 4, -43 }, { 186, 391, 56 },
            { 49, 20, -98 }, { 21, 398, -1 }, { 190, 259, -100 }, { 32, 322, 31 }, { 95, 235, 0 },
            { 273, 331, -79 }, { 185, 70, -54 }, { 195, 168, 44 }, { 40, 85, 70 }, { 323, 54, -73 },
            { 292, 126, -42 }, { 105, 91, 36 }, { 399, 362, -75 }, { 101, 248, -33 },
            { 258, 189, -35 }, { 43, 302, -48 }, { 58, 6, 54 }, { 336, 95, -81 }, { 46, 362, 17 },
            { 182, 184, 60 }, { 3, 348, -97 }, { 198, 350, 83 }, { 19, 159, 92 }, { 140, 246, 77 },
            { 89, 79, 77 }, { 104, 313, -93 }, { 305, 92, 54 }, { 35, 56, 98 }, { 158, 57, -70 },
            { 191, 28, -27 }, { 157, 276, 27 }, { 370, 289, -21 }, { 265, 166, -40 },
            { 181, 115, 36 }, { 399, 61, -66 }, { 313, 121, 25 }, { 355, 8, -17 }, { 138, 193, -2 },
            { 275, 371, -20 }, { 72, 141, -54 }, { 348, 131, -62 }, { 162, 236, 4 },
            { 363, 163, -55 }, { 133, 59, 9 }, { 278, 240, 21 }, { 308, 317, 93 }, { 42, 50, -58 },
            { 328, 216, -8 }, { 390, 348, 94 }, { 299, 99, -53 }, { 360, 22, -44 }, { 32, 252, 16 },
            { 120, 152, -31 }, { 6, 30, -2 }, { 307, 361, -80 }, { 254, 35, 46 }, { 345, 169, -51 },
            { 90, 294, 86 }, { 330, 155, -47 }, { 391, 124, -95 }, { 349, 39, 53 }, { 29, 132, 61 },
            { 130, 335, -64 }, { 117, 124, -48 }, { 201, 192, 99 }, { 394, 181, -83 },
            { 211, 347, -78 }, { 20, 42, 2 }, { 216, 132, 57 }, { 242, 125, -15 },
            { 330, 186, -16 }, { 23, 194, -36 }, { 25, 136, 31 }, { 199, 255, -41 },
            { 166, 188, -35 }, { 147, 356, -77 }, { 317, 166, 67 }, { 17, 184, -56 },
            { 205, 355, -67 }, { 176, 100, 42 }, { 251, 249, 60 }, { 60, 291, 21 },
            { 231, 341, -92 }, { 333, 234, -48 }, { 77, 387, -10 }, { 159, 238, 19 },
            { 59, 225, -74 }, { 242, 202, -18 }, { 162, 112, -68 }, { 136, 285, -49 },
            { 238, 170, 42 }, { 140, 388, -78 }, { 297, 177, 36 }, { 51, 37, -12 }, { 322, 9, -29 },
            { 370, 64, 96 }, { 342, 357, 46 }, { 364, 380, 81 }, { 66, 84, 17 }, { 286, 79, -63 },
            { 280, 109, 27 }, { 380, 317, -14 }, { 177, 217, 29 }, { 174, 181, 85 },
            { 307, 288, -82 }, { 198, 8, -38 }, { 51, 327, -5 }, { 324, 59, -13 }, { 285, 280, 60 },
            { 381, 382, -55 }, { 242, 257, -52 }, { 376, 334, -66 }, { 387, 129, -71 },
            { 186, 8, -55 }, { 188, 289, -12 }, { 274, 286, -61 }, { 211, 367, 78 },
            { 136, 319, 69 }, { 337, 1, -61 }, { 275, 82, -54 }, { 321, 199, 80 }, { 313, 51, -6 },
            { 8, 65, -97 }, { 60, 385, -40 }, { 148, 19, 8 }, { 273, 358, -59 }, { 233, 166, -5 },
            { 131, 136, 17 }, { 120, 289, 56 }, { 73, 272, 25 }, { 210, 296, -22 }, { 291, 9, 10 },
            { 29, 51, -97 }, { 43, 284, 76 }, { 340, 385, -52 }, { 187, 329, 88 }, { 212, 126, 99 },
            { 106, 247, -30 }, { 5, 34, 90 }, { 220, 223, 7 }, { 183, 221, -60 }, { 377, 101, 63 },
            { 30, 304, -72 }, { 285, 377, -24 }, { 368, 381, 9 }, { 33, 158, 29 }, { 349, 257, 84 },
            { 264, 232, 59 }, { 158, 64, -28 }, { 77, 347, 64 }, { 258, 257, 74 }, { 60, 33, 2 },
            { 150, 108, -21 }, { 367, 300, 2 }, { 115, 130, -79 }, { 124, 189, -39 },
            { 141, 299, 51 }, { 235, 19, -11 }, { 346, 309, -2 }, { 396, 344, -13 },
            { 273, 75, 83 }, { 74, 152, -3 }, { 196, 276, -39 }, { 105, 195, 55 }, { 47, 270, -8 },
            { 118, 53, 86 }, { 306, 218, -24 }, { 336, 260, -84 }, { 156, 345, 34 },
            { 354, 281, 56 }, { 282, 23, 63 }, { 308, 178, 25 }, { 367, 71, -31 }, { 225, 24, -26 },
            { 197, 175, -23 }, { 378, 108, -64 }, { 307, 37, -38 }, { 268, 247, 38 },
            { 352, 330, 63 }, { 110, 289, -63 }, { 200, 230, 25 }, { 207, 114, 49 },
            { 173, 243, -43 }, { 30, 360, -41 }, { 81, 270, 44 }, { 154, 168, 9 },
            { 193, 299, -24 }, { 92, 312, -10 }, { 261, 40, -1 }, { 322, 27, 30 },
            { 342, 197, -74 }, { 158, 334, 47 }, { 63, 194, -49 }, { 319, 67, 30 }, { 88, 10, 62 },
            { 255, 28, -67 }, { 112, 366, 82 }, { 254, 346, -92 }, { 218, 389, -19 },
            { 46, 70, -97 }, { 363, 338, -36 }, { 255, 271, 65 }, { 273, 21, -90 },
            { 76, 293, -30 }, { 246, 279, 11 }, { 102, 213, -53 }, { 245, 256, -13 },
            { 144, 134, -88 }, { 93, 235, 52 }, { 331, 211, 15 }, { 85, 316, 31 }, { 164, 74, 92 },
            { 304, 128, 91 }, { 300, 132, 89 }, { 114, 22, -2 }, { 231, 150, -74 },
            { 98, 237, -56 }, { 344, 71, -81 }, { 289, 30, -2 }, { 12, 82, -19 }, { 170, 283, -46 },
            { 4, 270, -52 }, { 316, 39, -58 }, { 328, 44, -22 }, { 36, 343, 76 }, { 41, 113, 56 },
            { 63, 329, -68 }, { 181, 180, -78 }, { 319, 228, -94 }, { 18, 330, -26 },
            { 269, 288, -31 }, { 387, 175, 80 }, { 207, 280, 78 }, { 207, 88, -33 },
            { 250, 109, 9 }, { 196, 55, -2 }, { 106, 44, -51 }, { 102, 254, -2 }, { 32, 82, -91 },
            { 318, 215, 89 }, { 61, 30, -40 }, { 351, 339, 81 }, { 349, 72, 65 }, { 27, 18, -91 },
            { 390, 305, 97 }, { 246, 130, -17 }, { 34, 43, 65 }, { 329, 43, -52 }, { 234, 9, 1 },
            { 27, 41, -64 }, { 4, 90, -50 }, { 350, 50, -76 }, { 35, 125, -92 }, { 316, 330, -52 },
            { 234, 257, 53 }, { 255, 201, -85 }, { 327, 66, -24 }, { 248, 49, -20 },
            { 76, 11, -73 }, { 77, 191, 3 }, { 289, 325, -60 }, { 265, 254, -30 },
            { 353, 304, -12 }, { 314, 362, 25 }, { 356, 292, 7 }, { 38, 382, 71 }, { 189, 168, 36 },
            { 189, 214, -71 }, { 307, 210, -99 }, { 262, 5, 10 }, { 84, 128, 26 }, { 99, 158, 16 },
            { 135, 102, -85 }, { 199, 173, 74 }, { 49, 105, 61 }, { 59, 150, -73 },
            { 220, 315, -44 }, { 332, 0, -71 }, { 340, 295, -81 }, { 71, 371, -47 },
            { 210, 31, 97 }, { 216, 335, -64 }, { 173, 228, -74 }, { 32, 15, 83 }, { 286, 342, 50 },
            { 38, 78, -14 }, { 52, 141, 32 }, { 65, 231, 60 }, { 377, 327, -91 }, { 387, 371, -48 },
            { 83, 162, 72 }, { 344, 207, -20 }, { 238, 299, -31 }, { 336, 108, -84 },
            { 216, 104, 36 }, { 91, 395, 74 }, { 301, 291, -27 }, { 243, 183, 64 },
            { 325, 216, 96 }, { 383, 21, 55 }, { 109, 193, -94 }, { 389, 26, -100 },
            { 178, 64, 96 }, { 80, 44, 93 }, { 179, 220, 0 }, { 3, 11, -79 }, { 296, 399, 21 },
            { 30, 113, -12 }, { 46, 15, 71 }, { 160, 343, -85 }, { 326, 43, -11 }, { 11, 122, 100 },
            { 14, 72, 9 }, { 95, 334, 8 }, { 158, 76, -8 }, { 65, 1, 65 }, { 342, 267, 1 },
            { 363, 243, -70 }, { 278, 48, 12 }, { 328, 180, 83 }, { 175, 270, 1 },
            { 144, 110, -54 }, { 26, 88, 83 }, { 2, 180, -84 }, { 278, 237, 44 }, { 321, 123, -10 },
            { 198, 39, 98 }, { 130, 136, 50 }, { 123, 278, 43 }, { 323, 43, 38 }, { 95, 72, 6 },
            { 126, 314, 31 }, { 386, 172, -32 }, { 319, 64, -48 }, { 121, 167, -6 },
            { 355, 23, 20 }, { 324, 198, -76 }, { 114, 259, -67 }, { 287, 116, 24 }, { 239, 17, 6 },
            { 333, 142, 73 }, { 318, 304, -38 }, { 305, 310, -13 }, { 70, 382, 59 },
            { 109, 148, 86 }, { 88, 342, -68 }, { 111, 52, -22 }, { 143, 216, -33 },
            { 73, 219, 46 }, { 154, 169, -98 }, { 321, 11, -23 }, { 390, 77, -6 }, { 90, 361, -21 },
            { 128, 98, 14 }, { 113, 397, -69 }, { 106, 95, -74 }, { 43, 42, 93 }, { 349, 156, 87 },
            { 205, 222, -29 }, { 207, 163, 56 }, { 317, 60, 19 }, { 53, 7, 6 }, { 232, 87, -30 },
            { 44, 324, -90 }, { 36, 257, -19 }, { 307, 87, -85 }, { 280, 229, 6 }, { 28, 383, 14 },
            { 265, 322, -59 }, { 3, 244, -24 }, { 87, 57, 12 }, { 302, 342, 51 }, { 104, 89, -22 },
            { 358, 361, 52 }, { 340, 200, 36 }, { 278, 15, -43 }, { 321, 260, 39 },
            { 259, 327, 84 }, { 97, 266, 47 }, { 284, 117, 10 }, { 201, 7, 19 }, { 323, 17, 17 },
            { 276, 317, 59 }, { 314, 4, 66 }, { 73, 280, -87 }, { 34, 287, -30 }, { 105, 113, 98 },
            { 337, 286, -5 }, { 380, 66, 56 }, { 227, 78, 23 }, { 396, 284, 91 }, { 179, 299, -50 },
            { 131, 229, 70 }, { 122, 269, -61 }, { 162, 165, 82 }, { 8, 67, -30 }, { 2, 50, -57 },
            { 257, 79, 86 }, { 175, 27, -98 }, { 155, 164, -52 }, { 242, 66, -40 }, { 22, 270, 63 },
            { 46, 301, -34 }, { 155, 48, -49 }, { 367, 398, 98 }, { 313, 212, 68 }, { 47, 369, 62 },
            { 189, 174, -49 }, { 153, 23, -54 }, { 193, 145, -70 }, { 194, 80, 53 },
            { 151, 342, -73 }, { 229, 317, -69 }, { 134, 330, 9 }, { 287, 230, 16 },
            { 245, 120, 92 }, { 60, 185, -15 }, { 374, 342, 79 }, { 208, 245, -18 },
            { 54, 244, 40 }, { 57, 246, 88 }, { 114, 145, 1 }, { 244, 337, 64 }, { 253, 288, -49 },
            { 61, 161, 65 }, { 368, 44, 51 }, { 251, 227, -97 }, { 306, 7, -56 }, { 12, 399, 62 },
            { 58, 9, 17 }, { 142, 120, 76 }, { 304, 87, -32 }, { 383, 213, 15 }, { 139, 65, 92 },
            { 134, 384, 55 }, { 119, 48, 0 }, { 178, 368, -9 }, { 102, 239, -77 }, { 322, 290, 29 },
            { 202, 58, -68 }, { 262, 205, 42 }, { 353, 133, 31 }, { 100, 5, -100 },
            { 224, 317, 36 }, { 110, 191, 41 }, { 36, 132, -45 }, { 83, 39, 62 }, { 245, 9, 51 },
            { 67, 94, 85 }, { 108, 246, 42 }, { 216, 248, 59 }, { 264, 334, 29 }, { 322, 164, -2 },
            { 221, 198, -11 }, { 3, 13, -8 }, { 157, 355, -2 }, { 123, 81, -18 }, { 153, 324, -63 },
            { 325, 239, -93 }, { 346, 193, 59 }, { 147, 198, -90 }, { 348, 196, 53 },
            { 134, 284, -58 }, { 332, 22, -24 }, { 65, 172, -75 }, { 243, 269, -12 },
            { 399, 19, 33 }, { 193, 101, -94 }, { 114, 204, -2 }, { 158, 173, 90 },
            { 350, 250, 53 }, { 397, 51, -37 }, { 118, 22, -75 }, { 355, 209, 39 },
            { 327, 137, 65 }, { 104, 282, 65 }, { 146, 220, 99 }, { 155, 304, -81 },
            { 271, 175, -71 }, { 60, 231, -91 }, { 63, 166, 75 }, { 181, 31, -45 },
            { 305, 298, -37 }, { 266, 77, -94 }, { 376, 190, 60 }, { 305, 124, 41 },
            { 315, 193, -40 }, { 195, 242, -66 }, { 14, 196, -66 }, { 149, 389, 31 },
            { 320, 59, -16 }, { 17, 192, -22 }, { 133, 265, -5 }, { 217, 240, 49 },
            { 118, 279, 48 }, { 142, 259, 52 }, { 246, 261, -20 }, { 268, 307, 36 },
            { 375, 373, 36 }, { 297, 319, 87 }, { 397, 67, -58 }, { 31, 59, 70 }, { 194, 121, -28 },
            { 311, 121, -93 }, { 347, 274, 60 }, { 199, 279, 31 }, { 137, 253, 1 }, { 302, 59, 92 },
            { 259, 309, 76 }, { 174, 268, 59 }, { 115, 222, 28 }, { 185, 67, 84 }, { 367, 81, -78 },
            { 256, 81, -16 }, { 297, 251, -100 }, { 233, 210, -72 }, { 234, 179, -41 },
            { 144, 163, 60 }, { 235, 203, 60 }, { 96, 175, -3 }, { 181, 266, -78 },
            { 210, 336, 92 }, { 90, 55, 97 }, { 326, 116, 95 }, { 116, 263, 45 }, { 368, 61, -69 },
            { 382, 314, 94 }, { 86, 270, 93 }, { 272, 18, 100 }, { 136, 386, 92 }, { 112, 294, 99 },
            { 368, 63, 9 }, { 37, 38, -63 }, { 91, 331, -45 }, { 302, 159, 9 }, { 359, 253, -81 },
            { 84, 146, -39 }, { 398, 263, 27 }, { 44, 16, -56 }, { 50, 322, 83 }, { 320, 312, 94 },
            { 122, 170, -75 }, { 223, 84, 67 }, { 333, 380, 82 }, { 211, 336, -73 },
            { 109, 29, 63 }, };
        double maxWeight = 10613;
        double minWeight = -10726;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 500 vertices and 1500 edges
     */
    @Test
    public void testGetMatching18()
    {
        int[][] edges = new int[][] { { 183, 286, 85 }, { 469, 315, -39 }, { 347, 142, 24 },
            { 374, 143, -82 }, { 375, 437, 28 }, { 463, 13, -61 }, { 131, 93, 42 },
            { 150, 328, 80 }, { 498, 104, 98 }, { 402, 231, -98 }, { 22, 295, 82 },
            { 121, 181, -12 }, { 314, 40, -22 }, { 82, 169, -90 }, { 219, 82, -98 },
            { 286, 182, -52 }, { 372, 208, -62 }, { 109, 269, -86 }, { 342, 247, -26 },
            { 209, 291, 79 }, { 295, 82, 56 }, { 465, 198, -58 }, { 82, 307, -37 },
            { 371, 207, -74 }, { 222, 467, -30 }, { 381, 75, -40 }, { 414, 408, 16 },
            { 262, 222, 20 }, { 97, 105, -44 }, { 431, 447, -63 }, { 210, 255, 91 },
            { 239, 244, 12 }, { 495, 187, -82 }, { 97, 440, 47 }, { 105, 475, -74 },
            { 125, 191, 49 }, { 371, 305, -50 }, { 255, 126, -80 }, { 267, 469, -35 },
            { 58, 360, 83 }, { 385, 198, -14 }, { 193, 203, -6 }, { 294, 272, -34 },
            { 246, 243, 35 }, { 195, 396, -64 }, { 492, 215, 81 }, { 340, 24, 72 },
            { 237, 361, -59 }, { 123, 384, -92 }, { 303, 460, -65 }, { 161, 25, -34 },
            { 336, 271, -33 }, { 294, 249, -21 }, { 424, 169, 4 }, { 387, 163, 7 },
            { 367, 91, -89 }, { 32, 424, 100 }, { 7, 394, -28 }, { 14, 232, 74 }, { 161, 100, -65 },
            { 387, 482, -16 }, { 440, 397, -80 }, { 46, 244, -72 }, { 48, 393, 64 },
            { 462, 36, -27 }, { 477, 445, 53 }, { 7, 311, 70 }, { 477, 414, -7 }, { 324, 202, -25 },
            { 477, 249, -17 }, { 170, 91, -87 }, { 6, 202, -43 }, { 125, 355, -19 },
            { 341, 58, 100 }, { 490, 296, 81 }, { 267, 101, 42 }, { 38, 492, -1 }, { 286, 391, 8 },
            { 414, 260, 43 }, { 391, 233, 98 }, { 106, 42, -43 }, { 90, 328, -77 },
            { 286, 479, -89 }, { 355, 69, 80 }, { 211, 107, -82 }, { 482, 472, -34 },
            { 323, 101, -65 }, { 401, 282, 33 }, { 77, 461, 60 }, { 151, 165, -65 },
            { 11, 129, -26 }, { 380, 479, -90 }, { 231, 493, -34 }, { 296, 369, -11 },
            { 35, 362, -84 }, { 492, 121, -31 }, { 135, 388, 35 }, { 480, 40, 71 }, { 2, 62, -87 },
            { 157, 105, 12 }, { 405, 230, -95 }, { 290, 279, 69 }, { 363, 321, -60 },
            { 373, 311, -95 }, { 97, 181, -18 }, { 6, 354, 30 }, { 431, 113, 77 }, { 356, 243, -7 },
            { 320, 469, -37 }, { 487, 471, -34 }, { 322, 158, 62 }, { 286, 199, -41 },
            { 13, 455, -16 }, { 34, 299, -40 }, { 465, 469, -89 }, { 366, 111, 88 },
            { 290, 460, -90 }, { 124, 271, -94 }, { 76, 231, -57 }, { 67, 162, -74 },
            { 31, 182, 31 }, { 114, 113, -20 }, { 252, 413, 47 }, { 41, 292, -65 },
            { 488, 139, 46 }, { 362, 150, 3 }, { 135, 340, 50 }, { 394, 5, 57 }, { 73, 395, -7 },
            { 245, 365, 72 }, { 205, 424, 84 }, { 491, 101, 97 }, { 119, 385, -81 },
            { 384, 19, 87 }, { 431, 3, -10 }, { 383, 105, 72 }, { 162, 63, -95 }, { 54, 474, -88 },
            { 492, 117, -21 }, { 372, 490, 48 }, { 286, 496, -21 }, { 218, 437, 46 },
            { 50, 487, -70 }, { 300, 307, 87 }, { 441, 60, -78 }, { 316, 273, -90 },
            { 428, 111, -67 }, { 100, 253, 15 }, { 206, 329, -26 }, { 147, 211, 24 },
            { 112, 356, -65 }, { 316, 335, -67 }, { 497, 465, 33 }, { 314, 246, -72 },
            { 353, 432, -88 }, { 244, 130, -79 }, { 64, 232, 91 }, { 338, 372, -84 },
            { 128, 265, 68 }, { 170, 496, 90 }, { 346, 73, 44 }, { 288, 139, -59 },
            { 328, 225, -20 }, { 480, 206, -17 }, { 468, 387, -23 }, { 93, 43, 28 },
            { 252, 435, -30 }, { 315, 12, 13 }, { 218, 496, 90 }, { 291, 353, -59 },
            { 17, 384, -66 }, { 375, 163, -46 }, { 37, 311, 71 }, { 107, 260, 75 },
            { 271, 232, -20 }, { 117, 64, 71 }, { 144, 123, 68 }, { 312, 424, -2 }, { 479, 29, 45 },
            { 386, 392, -76 }, { 77, 60, 98 }, { 233, 468, -11 }, { 387, 457, -28 }, { 68, 0, 7 },
            { 289, 457, -33 }, { 350, 419, 0 }, { 241, 237, 49 }, { 217, 165, 39 },
            { 344, 15, -13 }, { 445, 109, 8 }, { 353, 495, 99 }, { 241, 466, -44 },
            { 236, 410, -54 }, { 202, 181, 27 }, { 306, 144, 37 }, { 328, 313, -92 },
            { 353, 339, 37 }, { 297, 149, -62 }, { 87, 92, -16 }, { 483, 72, -71 }, { 431, 70, 48 },
            { 343, 428, -59 }, { 20, 266, 90 }, { 455, 131, -76 }, { 348, 139, 96 },
            { 461, 266, -62 }, { 457, 59, 29 }, { 342, 415, -2 }, { 171, 312, -56 },
            { 277, 354, -91 }, { 142, 483, -87 }, { 249, 470, -28 }, { 158, 480, -3 },
            { 100, 32, 23 }, { 219, 90, -10 }, { 458, 485, -94 }, { 324, 257, 70 }, { 168, 9, 26 },
            { 390, 249, -89 }, { 313, 212, 11 }, { 170, 460, 22 }, { 394, 183, -58 },
            { 74, 0, -74 }, { 121, 66, 69 }, { 139, 74, -17 }, { 356, 365, -3 }, { 404, 413, 17 },
            { 385, 172, 73 }, { 378, 247, -92 }, { 341, 443, -76 }, { 436, 348, -20 },
            { 205, 65, -97 }, { 309, 484, 86 }, { 302, 375, 16 }, { 103, 327, -81 },
            { 397, 357, 86 }, { 14, 138, 11 }, { 477, 85, 16 }, { 457, 253, 20 }, { 351, 292, 54 },
            { 411, 295, 57 }, { 149, 493, 97 }, { 170, 282, -47 }, { 188, 442, 79 },
            { 224, 347, -96 }, { 392, 181, 46 }, { 79, 423, 81 }, { 89, 222, 32 }, { 78, 142, -63 },
            { 278, 423, 25 }, { 71, 144, 14 }, { 96, 442, -84 }, { 431, 59, 18 }, { 57, 465, 33 },
            { 57, 128, -1 }, { 290, 276, -51 }, { 403, 161, 17 }, { 323, 446, 17 },
            { 115, 333, 60 }, { 481, 80, 48 }, { 88, 377, 51 }, { 112, 474, 69 }, { 282, 375, -60 },
            { 186, 414, 15 }, { 75, 281, -45 }, { 194, 440, 81 }, { 235, 116, -82 },
            { 206, 423, 0 }, { 459, 457, -66 }, { 43, 481, -55 }, { 497, 471, 91 },
            { 494, 282, 61 }, { 51, 242, -43 }, { 136, 360, -4 }, { 14, 119, -97 }, { 497, 162, 6 },
            { 381, 481, -11 }, { 117, 442, 98 }, { 354, 35, 57 }, { 139, 177, 23 },
            { 460, 495, -18 }, { 438, 374, 73 }, { 437, 394, -94 }, { 393, 69, -100 },
            { 313, 225, -40 }, { 294, 288, 98 }, { 431, 63, -69 }, { 498, 350, 76 },
            { 239, 499, -72 }, { 300, 32, 63 }, { 441, 160, -51 }, { 375, 345, 17 },
            { 393, 263, 66 }, { 84, 438, 40 }, { 327, 437, -96 }, { 36, 54, 86 }, { 73, 269, -66 },
            { 350, 405, 12 }, { 14, 368, -35 }, { 272, 423, 70 }, { 193, 106, -81 },
            { 267, 399, -89 }, { 110, 456, -63 }, { 211, 333, -71 }, { 32, 208, -65 },
            { 125, 221, -1 }, { 103, 212, 35 }, { 396, 365, -62 }, { 467, 374, -8 },
            { 213, 437, -1 }, { 406, 115, -10 }, { 106, 205, 36 }, { 238, 243, -48 },
            { 132, 106, -73 }, { 243, 160, -62 }, { 57, 341, -78 }, { 479, 198, 48 },
            { 138, 289, -82 }, { 386, 437, 57 }, { 181, 126, 7 }, { 244, 300, 6 },
            { 136, 347, -36 }, { 272, 266, -84 }, { 15, 464, 58 }, { 55, 124, -95 },
            { 192, 416, 65 }, { 89, 378, -12 }, { 485, 66, 50 }, { 228, 140, 28 },
            { 443, 476, -19 }, { 158, 167, 100 }, { 373, 492, -60 }, { 303, 251, 28 },
            { 142, 94, -69 }, { 175, 32, -71 }, { 327, 206, 18 }, { 372, 61, 68 }, { 424, 259, 77 },
            { 284, 356, 12 }, { 293, 468, 3 }, { 433, 403, -6 }, { 499, 206, 98 },
            { 478, 234, -14 }, { 180, 350, 73 }, { 29, 38, 76 }, { 265, 480, -67 },
            { 165, 253, 85 }, { 245, 334, 54 }, { 4, 414, -55 }, { 493, 267, 67 }, { 281, 324, 93 },
            { 397, 393, -12 }, { 62, 232, 38 }, { 75, 176, 34 }, { 465, 244, -34 },
            { 218, 260, -35 }, { 409, 371, -54 }, { 235, 463, 90 }, { 376, 116, 99 },
            { 346, 167, 58 }, { 303, 204, -79 }, { 498, 249, -57 }, { 436, 454, 17 },
            { 297, 403, -25 }, { 275, 10, 39 }, { 456, 407, 51 }, { 280, 312, -99 },
            { 477, 321, 62 }, { 421, 239, 81 }, { 181, 499, -21 }, { 408, 472, 30 },
            { 348, 327, 54 }, { 448, 367, 77 }, { 162, 312, -22 }, { 397, 468, -7 },
            { 100, 112, 78 }, { 320, 238, 57 }, { 227, 297, -14 }, { 167, 126, -1 }, { 8, 70, 65 },
            { 460, 69, -86 }, { 476, 452, -61 }, { 236, 46, -65 }, { 26, 489, -46 },
            { 159, 142, 27 }, { 239, 29, -15 }, { 406, 413, 95 }, { 408, 123, -34 },
            { 169, 115, -70 }, { 86, 302, -97 }, { 206, 54, 33 }, { 157, 41, -12 }, { 105, 294, 1 },
            { 251, 235, 41 }, { 201, 250, 89 }, { 300, 262, 37 }, { 390, 440, 11 },
            { 334, 174, -21 }, { 164, 447, 62 }, { 402, 393, 48 }, { 156, 307, -54 },
            { 411, 242, -28 }, { 114, 66, 75 }, { 466, 254, 38 }, { 147, 426, -38 },
            { 203, 421, -12 }, { 407, 67, -77 }, { 335, 45, -52 }, { 433, 278, 84 },
            { 70, 372, 51 }, { 397, 250, -47 }, { 82, 29, -92 }, { 422, 201, 91 }, { 372, 44, -48 },
            { 25, 14, 33 }, { 379, 149, 17 }, { 389, 185, 23 }, { 498, 81, -70 }, { 133, 280, 47 },
            { 271, 246, -31 }, { 214, 344, 23 }, { 273, 393, 4 }, { 49, 47, -94 }, { 433, 70, 48 },
            { 141, 28, -85 }, { 247, 324, 34 }, { 60, 399, 74 }, { 15, 73, -21 }, { 131, 58, 69 },
            { 71, 308, -3 }, { 151, 24, 96 }, { 284, 28, 73 }, { 286, 497, -90 }, { 365, 495, 6 },
            { 166, 481, -27 }, { 321, 212, 5 }, { 264, 38, 67 }, { 191, 214, -82 }, { 16, 40, 70 },
            { 466, 374, 39 }, { 88, 75, 97 }, { 216, 139, -73 }, { 98, 475, 55 }, { 169, 183, -62 },
            { 154, 179, -29 }, { 172, 176, 95 }, { 280, 331, 52 }, { 52, 119, 87 },
            { 102, 318, -18 }, { 242, 205, 55 }, { 326, 339, -2 }, { 66, 116, 26 },
            { 443, 407, -58 }, { 383, 116, 53 }, { 403, 444, -76 }, { 400, 142, -27 },
            { 391, 380, 11 }, { 472, 368, -10 }, { 326, 109, 68 }, { 334, 267, -19 },
            { 187, 390, -34 }, { 49, 365, -88 }, { 63, 337, -9 }, { 409, 130, -78 },
            { 82, 224, 73 }, { 391, 360, -79 }, { 400, 370, 54 }, { 400, 310, -57 },
            { 423, 475, 91 }, { 372, 30, 99 }, { 143, 394, 67 }, { 146, 410, 5 }, { 190, 26, -61 },
            { 343, 372, 44 }, { 468, 434, -30 }, { 281, 352, 9 }, { 377, 485, -62 },
            { 180, 363, 30 }, { 18, 485, 52 }, { 258, 425, 9 }, { 29, 148, 97 }, { 438, 423, 28 },
            { 49, 400, 43 }, { 437, 265, -4 }, { 365, 231, 93 }, { 283, 197, 29 },
            { 111, 411, -57 }, { 100, 334, 88 }, { 148, 365, 69 }, { 258, 140, -77 },
            { 122, 168, 50 }, { 497, 356, -37 }, { 201, 380, -29 }, { 300, 89, -47 },
            { 342, 32, 72 }, { 219, 220, 74 }, { 468, 253, -46 }, { 381, 285, 8 }, { 341, 35, 99 },
            { 272, 307, 17 }, { 24, 358, -38 }, { 338, 289, 23 }, { 56, 253, -32 },
            { 374, 189, -49 }, { 453, 373, -87 }, { 475, 234, 67 }, { 325, 338, -98 },
            { 116, 45, 69 }, { 122, 489, -13 }, { 84, 273, -17 }, { 370, 313, -59 },
            { 360, 314, 33 }, { 251, 363, -87 }, { 243, 377, -30 }, { 483, 191, 42 },
            { 181, 146, 54 }, { 378, 164, 33 }, { 58, 250, 33 }, { 134, 30, 7 }, { 492, 337, -8 },
            { 87, 455, 95 }, { 319, 454, -10 }, { 224, 16, -76 }, { 93, 272, 22 },
            { 397, 318, -78 }, { 202, 73, -77 }, { 79, 172, -35 }, { 465, 432, -53 },
            { 217, 498, 30 }, { 183, 332, 42 }, { 323, 94, 18 }, { 388, 79, -59 },
            { 192, 458, -95 }, { 331, 296, 89 }, { 176, 126, 56 }, { 266, 24, 27 },
            { 283, 478, -99 }, { 482, 302, 36 }, { 137, 319, 87 }, { 492, 81, 30 },
            { 306, 138, 90 }, { 225, 422, 29 }, { 352, 34, 80 }, { 302, 114, -15 }, { 498, 71, 97 },
            { 391, 54, 9 }, { 155, 18, 83 }, { 404, 57, 37 }, { 492, 403, 85 }, { 378, 306, 15 },
            { 118, 235, -83 }, { 152, 155, -82 }, { 36, 203, 19 }, { 489, 48, -43 },
            { 292, 442, 77 }, { 129, 296, -63 }, { 384, 114, -98 }, { 21, 256, 53 },
            { 214, 134, 72 }, { 320, 288, -46 }, { 483, 225, 61 }, { 190, 183, 84 },
            { 372, 314, -34 }, { 351, 386, -52 }, { 362, 163, 51 }, { 213, 469, 48 },
            { 305, 136, 9 }, { 91, 450, -62 }, { 164, 353, -43 }, { 194, 469, 22 }, { 22, 125, 45 },
            { 36, 432, -32 }, { 459, 337, 8 }, { 58, 210, -70 }, { 96, 20, -57 }, { 449, 2, -5 },
            { 352, 497, -19 }, { 236, 363, 45 }, { 281, 111, -3 }, { 404, 220, -65 },
            { 105, 26, 62 }, { 490, 209, -93 }, { 489, 110, -51 }, { 237, 248, -6 },
            { 439, 44, -57 }, { 251, 41, 57 }, { 335, 385, -39 }, { 461, 322, -36 },
            { 152, 327, 95 }, { 136, 230, 54 }, { 71, 248, -11 }, { 70, 191, -8 },
            { 308, 117, -100 }, { 249, 205, -15 }, { 92, 116, -6 }, { 116, 337, -8 },
            { 354, 477, -46 }, { 191, 150, -100 }, { 97, 291, 31 }, { 463, 279, 84 },
            { 462, 356, 97 }, { 214, 12, -23 }, { 146, 353, 43 }, { 100, 454, 21 }, { 35, 32, -54 },
            { 387, 190, -99 }, { 351, 223, 2 }, { 280, 341, 35 }, { 44, 479, -10 }, { 49, 58, 56 },
            { 157, 313, -55 }, { 57, 167, -31 }, { 229, 463, 58 }, { 366, 188, 69 },
            { 394, 353, -39 }, { 90, 157, 34 }, { 89, 30, 84 }, { 437, 134, -55 }, { 12, 401, 87 },
            { 97, 400, -49 }, { 43, 365, 81 }, { 43, 471, -87 }, { 323, 124, -2 }, { 389, 126, 39 },
            { 79, 439, 23 }, { 288, 42, 35 }, { 237, 498, -89 }, { 248, 458, -42 },
            { 141, 325, -5 }, { 393, 490, 35 }, { 88, 483, -17 }, { 152, 47, -52 }, { 467, 1, 45 },
            { 102, 126, 92 }, { 360, 250, -47 }, { 312, 120, 28 }, { 65, 361, 52 },
            { 436, 225, 89 }, { 390, 75, 94 }, { 422, 243, 4 }, { 450, 13, -76 }, { 464, 48, 75 },
            { 157, 348, -82 }, { 258, 61, -9 }, { 22, 390, -74 }, { 26, 14, 5 }, { 403, 37, -3 },
            { 197, 97, -12 }, { 495, 214, -48 }, { 331, 163, -44 }, { 126, 426, 5 },
            { 316, 20, -70 }, { 426, 304, -87 }, { 61, 362, -47 }, { 296, 32, -87 },
            { 105, 337, -82 }, { 352, 63, 40 }, { 145, 382, -15 }, { 201, 360, -8 },
            { 42, 173, 56 }, { 296, 294, -85 }, { 196, 220, 22 }, { 41, 334, 36 }, { 10, 147, -79 },
            { 499, 88, 37 }, { 400, 448, -35 }, { 25, 17, 50 }, { 233, 39, 6 }, { 10, 99, -34 },
            { 303, 314, 94 }, { 262, 264, -51 }, { 183, 361, 44 }, { 408, 251, 45 },
            { 497, 196, 64 }, { 314, 333, 3 }, { 206, 285, -19 }, { 127, 311, 99 }, { 495, 24, 31 },
            { 484, 464, 26 }, { 323, 334, 6 }, { 294, 481, -35 }, { 220, 226, -36 },
            { 286, 446, -41 }, { 312, 237, -87 }, { 246, 472, 6 }, { 225, 68, -94 },
            { 195, 393, 27 }, { 5, 345, 28 }, { 368, 179, -86 }, { 339, 267, 40 }, { 345, 300, 27 },
            { 261, 447, 39 }, { 491, 284, 50 }, { 227, 127, -6 }, { 363, 373, 95 },
            { 111, 306, 20 }, { 428, 324, 56 }, { 83, 160, -82 }, { 134, 117, -21 },
            { 72, 166, -15 }, { 64, 481, -14 }, { 148, 61, -65 }, { 221, 157, -2 },
            { 442, 55, -68 }, { 78, 413, -2 }, { 436, 182, -38 }, { 91, 73, 54 }, { 468, 177, -15 },
            { 232, 295, -91 }, { 299, 4, -96 }, { 26, 94, 17 }, { 375, 139, 19 }, { 281, 55, 32 },
            { 420, 262, -48 }, { 472, 358, -35 }, { 289, 39, 64 }, { 418, 263, -35 },
            { 372, 308, 76 }, { 143, 381, 70 }, { 355, 378, 82 }, { 415, 490, -25 },
            { 423, 73, -79 }, { 99, 156, 82 }, { 118, 151, 17 }, { 490, 462, -60 },
            { 64, 443, -31 }, { 268, 47, 55 }, { 139, 338, 46 }, { 297, 112, 80 }, { 108, 16, 97 },
            { 187, 277, 6 }, { 265, 227, 65 }, { 170, 385, 100 }, { 300, 405, -47 },
            { 249, 45, -5 }, { 163, 167, 24 }, { 428, 485, -85 }, { 345, 117, -42 },
            { 96, 368, 31 }, { 289, 203, -50 }, { 5, 107, 50 }, { 13, 348, 17 }, { 103, 4, -97 },
            { 450, 335, -23 }, { 56, 172, -4 }, { 358, 59, -55 }, { 385, 441, -53 },
            { 89, 334, 18 }, { 206, 189, 42 }, { 476, 493, -76 }, { 43, 480, 76 }, { 275, 201, -4 },
            { 424, 176, 46 }, { 386, 301, -14 }, { 64, 418, 19 }, { 85, 403, -62 },
            { 349, 52, -66 }, { 279, 328, -25 }, { 490, 88, -54 }, { 113, 256, 29 },
            { 398, 379, -50 }, { 327, 266, 71 }, { 117, 467, -33 }, { 344, 357, -69 },
            { 284, 481, 0 }, { 121, 486, 97 }, { 209, 140, 6 }, { 426, 188, -8 }, { 346, 109, 27 },
            { 137, 425, -26 }, { 126, 403, -9 }, { 99, 210, -62 }, { 230, 125, -99 },
            { 134, 142, 34 }, { 141, 81, -82 }, { 223, 123, 77 }, { 67, 417, -74 }, { 42, 94, 12 },
            { 418, 359, -88 }, { 436, 219, -94 }, { 491, 307, 48 }, { 95, 151, -66 },
            { 415, 95, 35 }, { 73, 228, 100 }, { 204, 69, 77 }, { 98, 102, -75 }, { 426, 232, -38 },
            { 215, 245, -65 }, { 348, 356, -63 }, { 25, 23, 33 }, { 181, 345, 65 },
            { 133, 419, 40 }, { 104, 401, -52 }, { 208, 273, 8 }, { 238, 9, 48 }, { 261, 4, 33 },
            { 247, 249, -76 }, { 397, 25, 40 }, { 45, 38, -38 }, { 464, 422, -40 }, { 337, 76, 11 },
            { 142, 219, 97 }, { 56, 244, 13 }, { 376, 127, -17 }, { 76, 311, -74 }, { 4, 85, 89 },
            { 484, 133, 20 }, { 254, 288, 10 }, { 415, 25, 13 }, { 132, 117, -16 }, { 44, 161, 95 },
            { 472, 65, -46 }, { 35, 91, -67 }, { 168, 462, 48 }, { 431, 13, 90 }, { 138, 493, -90 },
            { 185, 118, -22 }, { 317, 12, 84 }, { 55, 358, 76 }, { 247, 64, 91 }, { 80, 296, 23 },
            { 68, 418, -32 }, { 339, 317, -59 }, { 219, 339, -2 }, { 474, 375, 73 },
            { 68, 250, -61 }, { 216, 410, -61 }, { 281, 304, -26 }, { 477, 391, -1 },
            { 492, 357, -79 }, { 390, 183, -66 }, { 124, 130, -67 }, { 252, 491, -42 },
            { 275, 457, 97 }, { 182, 345, 64 }, { 283, 33, -97 }, { 362, 313, -28 },
            { 353, 226, -14 }, { 286, 352, 65 }, { 487, 303, -42 }, { 83, 348, 3 },
            { 137, 338, 26 }, { 386, 242, -64 }, { 155, 432, 32 }, { 220, 136, 24 },
            { 288, 187, -17 }, { 148, 102, 82 }, { 9, 143, 5 }, { 410, 154, 72 }, { 146, 415, -20 },
            { 138, 402, -45 }, { 465, 364, -88 }, { 252, 175, -21 }, { 366, 255, 61 },
            { 82, 120, -62 }, { 239, 377, 67 }, { 380, 308, 24 }, { 373, 95, -22 }, { 98, 491, 43 },
            { 86, 474, -66 }, { 316, 389, -85 }, { 420, 471, -74 }, { 186, 172, 82 },
            { 370, 114, -84 }, { 95, 108, 1 }, { 365, 217, 65 }, { 112, 273, -51 },
            { 333, 123, -14 }, { 220, 125, -13 }, { 24, 299, -9 }, { 161, 47, -5 },
            { 483, 451, 60 }, { 135, 122, 29 }, { 216, 313, 30 }, { 417, 382, -72 },
            { 92, 228, 95 }, { 78, 147, 88 }, { 125, 273, 4 }, { 433, 150, -16 }, { 342, 211, 32 },
            { 343, 89, -61 }, { 74, 80, -70 }, { 240, 358, 41 }, { 378, 34, 45 }, { 493, 181, -54 },
            { 419, 194, 64 }, { 177, 218, -87 }, { 446, 43, 64 }, { 382, 128, -42 },
            { 477, 290, -81 }, { 317, 490, 34 }, { 478, 381, 4 }, { 452, 178, 87 },
            { 47, 469, -86 }, { 299, 180, 75 }, { 50, 100, -92 }, { 254, 337, 7 }, { 57, 459, 37 },
            { 142, 445, 91 }, { 152, 248, -89 }, { 470, 93, -37 }, { 14, 86, -6 },
            { 264, 105, -36 }, { 185, 169, 0 }, { 288, 200, 50 }, { 145, 444, 43 },
            { 259, 245, -54 }, { 43, 281, 96 }, { 219, 218, 93 }, { 5, 480, -67 }, { 110, 26, -38 },
            { 178, 343, -2 }, { 29, 292, 19 }, { 472, 158, -95 }, { 351, 137, 0 }, { 269, 345, 78 },
            { 45, 118, -34 }, { 413, 205, -52 }, { 240, 495, -51 }, { 475, 467, -64 },
            { 353, 147, 3 }, { 80, 198, 15 }, { 420, 229, -2 }, { 141, 241, 61 }, { 223, 274, 22 },
            { 156, 305, 72 }, { 441, 72, -6 }, { 129, 196, 24 }, { 198, 165, 87 }, { 416, 25, 22 },
            { 149, 196, -47 }, { 290, 333, 81 }, { 13, 480, -20 }, { 397, 286, -4 },
            { 171, 334, -49 }, { 385, 275, 0 }, { 408, 49, 38 }, { 317, 57, 49 }, { 422, 111, -15 },
            { 348, 0, -94 }, { 409, 55, 3 }, { 368, 488, -61 }, { 315, 285, -87 }, { 403, 341, 40 },
            { 394, 174, 44 }, { 96, 185, -33 }, { 38, 464, -29 }, { 341, 417, 79 },
            { 234, 175, -23 }, { 386, 182, 81 }, { 39, 184, -81 }, { 42, 124, 43 },
            { 351, 258, -43 }, { 264, 68, 56 }, { 339, 447, -98 }, { 337, 190, -1 },
            { 319, 310, -100 }, { 380, 350, 31 }, { 474, 22, 0 }, { 453, 124, -79 },
            { 314, 1, -54 }, { 389, 109, 44 }, { 428, 210, 70 }, { 338, 228, -73 },
            { 400, 398, -42 }, { 439, 484, 36 }, { 75, 194, -75 }, { 295, 207, -33 },
            { 445, 57, -35 }, { 6, 323, -48 }, { 225, 413, 54 }, { 268, 408, -81 }, { 72, 58, 17 },
            { 105, 27, 60 }, { 59, 84, -97 }, { 252, 335, 83 }, { 50, 277, 92 }, { 253, 481, 77 },
            { 453, 290, 77 }, { 303, 155, -93 }, { 257, 132, 54 }, { 191, 132, 98 },
            { 52, 411, -70 }, { 250, 4, -27 }, { 499, 494, 27 }, { 122, 1, -21 }, { 288, 177, -40 },
            { 79, 336, 36 }, { 465, 324, -66 }, { 112, 396, 25 }, { 488, 458, -17 },
            { 106, 99, -2 }, { 5, 54, -20 }, { 355, 287, -54 }, { 113, 360, -62 }, { 299, 112, 4 },
            { 447, 110, -55 }, { 51, 190, 9 }, { 476, 284, 21 }, { 462, 157, 93 },
            { 106, 298, -58 }, { 212, 394, -8 }, { 374, 449, 94 }, { 409, 17, -53 },
            { 255, 137, -44 }, { 115, 309, 16 }, { 301, 373, -31 }, { 299, 455, -2 },
            { 322, 239, -80 }, { 332, 450, 46 }, { 38, 85, -51 }, { 112, 478, 86 },
            { 294, 215, -47 }, { 463, 107, -95 }, { 256, 303, 53 }, { 342, 313, 61 },
            { 368, 226, -64 }, { 433, 93, -48 }, { 257, 337, 99 }, { 192, 486, -83 },
            { 45, 64, -78 }, { 450, 369, 2 }, { 82, 153, 57 }, { 426, 333, -15 }, { 210, 52, -16 },
            { 459, 147, -36 }, { 241, 77, 31 }, { 262, 465, -41 }, { 186, 250, -35 },
            { 23, 13, -77 }, { 103, 406, 67 }, { 480, 236, -56 }, { 160, 387, -67 },
            { 436, 486, 42 }, { 426, 416, 60 }, { 363, 440, 21 }, { 44, 485, -92 },
            { 169, 497, -48 }, { 170, 86, -10 }, { 345, 366, 19 }, { 53, 454, -74 },
            { 496, 210, -18 }, { 186, 340, -68 }, { 138, 484, -49 }, { 418, 136, 42 },
            { 239, 190, -78 }, { 22, 196, 36 }, { 33, 461, -12 }, { 71, 395, -29 }, { 89, 313, 96 },
            { 160, 386, 46 }, { 228, 311, 81 }, { 135, 325, 17 }, { 236, 269, -63 },
            { 465, 85, 27 }, { 279, 458, -14 }, { 70, 483, 29 }, { 383, 323, 85 }, { 468, 75, -82 },
            { 458, 221, -38 }, { 230, 67, -5 }, { 67, 471, -13 }, { 4, 430, 60 }, { 61, 180, -55 },
            { 440, 470, -52 }, { 264, 215, -66 }, { 154, 499, -71 }, { 343, 283, -55 },
            { 135, 113, -12 }, { 321, 25, -61 }, { 52, 249, 78 }, { 462, 190, 69 },
            { 312, 58, -61 }, { 100, 409, -54 }, { 239, 326, 80 }, { 200, 321, -6 },
            { 251, 380, -97 }, { 334, 66, -40 }, { 349, 145, 8 }, { 461, 482, -59 },
            { 21, 401, -5 }, { 66, 192, 17 }, { 145, 176, 56 }, { 99, 175, 25 }, { 30, 77, -22 },
            { 451, 211, 10 }, { 52, 383, -97 }, { 496, 4, 76 }, { 387, 34, -52 }, { 189, 167, 88 },
            { 402, 224, 99 }, { 77, 414, -30 }, { 144, 488, 90 }, { 87, 255, 7 }, { 388, 87, -60 },
            { 315, 351, 63 }, { 312, 241, -72 }, { 149, 140, -24 }, { 465, 249, 9 },
            { 244, 57, 29 }, { 70, 328, 84 }, { 25, 105, 59 }, { 499, 203, -28 }, { 421, 99, 64 },
            { 232, 332, 74 }, { 393, 75, 2 }, { 256, 244, -21 }, { 384, 25, 2 }, { 96, 309, -79 },
            { 429, 371, -39 }, { 237, 349, 51 }, { 9, 211, -11 }, { 390, 240, -2 },
            { 14, 132, -13 }, { 490, 102, 83 }, { 81, 120, -3 }, { 39, 101, -39 }, { 213, 94, 55 },
            { 321, 494, -8 }, { 383, 80, 86 }, { 453, 84, -24 }, { 298, 239, -84 },
            { 302, 453, 34 }, { 292, 337, 56 }, { 217, 469, 63 }, { 94, 447, 25 }, { 84, 420, -31 },
            { 292, 115, -26 }, { 188, 135, -23 }, { 256, 203, -64 }, { 188, 489, -38 },
            { 377, 359, 38 }, { 209, 323, 63 }, { 346, 408, -63 }, { 187, 218, 25 },
            { 360, 62, 49 }, { 391, 495, -43 }, { 228, 151, -41 }, { 158, 297, 44 },
            { 405, 393, 9 }, { 61, 170, -24 }, { 65, 70, -10 }, { 251, 246, -1 }, { 253, 181, 30 },
            { 432, 129, -74 }, { 23, 79, 47 }, { 135, 211, -49 }, { 216, 74, 30 }, { 310, 249, 62 },
            { 150, 1, -67 }, { 187, 377, 82 }, { 131, 146, -92 }, { 350, 370, -19 },
            { 162, 144, -97 }, { 170, 38, -36 }, { 473, 477, 65 }, { 33, 240, -90 },
            { 128, 195, -30 }, { 375, 93, 11 }, { 237, 220, -53 }, { 337, 490, -13 },
            { 212, 147, -88 }, { 498, 338, 52 }, { 344, 145, 15 }, { 374, 361, 31 },
            { 442, 197, 92 }, { 362, 161, 91 }, { 381, 355, 89 }, { 291, 404, -2 },
            { 182, 359, -74 }, { 326, 254, -56 }, { 430, 64, -81 }, { 60, 8, -2 },
            { 166, 283, -19 }, { 203, 269, -46 }, { 34, 433, -52 }, { 108, 111, -58 },
            { 281, 33, -22 }, { 86, 220, 76 }, { 183, 303, 56 }, { 226, 495, -68 },
            { 368, 91, -78 }, { 160, 266, -94 }, { 276, 66, -26 }, { 198, 489, -31 },
            { 431, 169, 80 }, { 255, 332, 78 }, { 227, 448, -33 }, { 363, 389, 9 }, { 91, 298, -2 },
            { 117, 160, -51 }, { 154, 105, -2 }, { 241, 347, -91 }, { 59, 327, 89 },
            { 114, 285, -40 }, { 143, 438, 81 }, { 446, 217, 65 }, { 177, 249, -91 },
            { 436, 466, 97 }, { 398, 239, -17 }, { 42, 446, 65 }, { 385, 153, -52 },
            { 261, 473, 1 }, { 227, 39, -64 }, { 150, 67, -50 }, { 487, 171, -76 },
            { 177, 432, -92 }, { 283, 174, -52 }, { 487, 250, 53 }, { 207, 394, -85 },
            { 207, 235, -24 }, { 79, 252, -20 }, { 405, 293, -73 }, { 218, 5, 3 }, { 187, 83, -60 },
            { 345, 258, -30 }, { 356, 290, -12 }, { 388, 426, 25 }, { 287, 420, 7 },
            { 280, 406, 71 }, { 151, 351, 36 }, { 198, 108, -71 }, { 317, 60, -99 },
            { 131, 432, 10 }, { 354, 33, 26 }, { 447, 66, 16 }, { 361, 356, -85 }, { 295, 374, 74 },
            { 464, 342, 61 }, { 401, 164, -73 }, { 49, 285, -44 }, { 363, 323, -71 },
            { 428, 161, -81 }, { 80, 71, -47 }, { 418, 461, 97 }, { 181, 433, -64 },
            { 161, 11, -74 }, { 204, 47, 83 }, { 142, 333, 50 }, { 316, 257, -14 },
            { 447, 335, 32 }, { 141, 447, 60 }, { 247, 476, -91 }, { 347, 248, -48 },
            { 42, 485, 72 }, { 204, 266, -20 }, { 65, 210, -31 }, { 214, 58, -84 },
            { 337, 432, 36 }, { 469, 177, 74 }, { 145, 232, -27 }, { 174, 160, 64 },
            { 226, 446, 96 }, { 281, 129, 55 }, { 134, 349, -94 }, { 444, 215, -100 },
            { 322, 456, 96 }, { 408, 341, 93 }, { 177, 465, 0 }, { 471, 473, -79 },
            { 316, 233, 21 }, { 6, 122, -12 }, { 419, 116, 71 }, { 344, 366, -85 },
            { 419, 402, -11 }, { 359, 68, 100 }, { 65, 378, 9 }, { 23, 478, 8 }, { 383, 281, -8 },
            { 73, 302, 65 }, { 181, 486, 1 }, { 298, 156, -70 }, { 326, 429, 12 }, { 271, 323, 83 },
            { 372, 45, 1 }, { 119, 235, -54 }, { 485, 294, 83 }, { 214, 245, -84 }, { 204, 71, 44 },
            { 180, 380, -10 }, { 303, 31, 98 }, { 191, 36, 50 }, { 254, 354, 43 }, { 368, 401, 38 },
            { 227, 342, 6 }, { 56, 446, 31 }, { 79, 432, -32 }, { 414, 118, -48 }, { 100, 408, -6 },
            { 52, 474, 20 }, { 156, 176, -76 }, { 459, 140, -67 }, { 42, 304, 24 }, { 338, 188, 6 },
            { 420, 149, 73 }, { 62, 244, -38 }, { 105, 208, -13 }, { 199, 413, 59 },
            { 391, 197, 86 }, { 137, 291, -68 }, { 147, 308, -22 }, { 271, 481, -33 },
            { 263, 222, 46 }, { 275, 226, -98 }, { 272, 284, -23 }, { 170, 74, -6 },
            { 296, 164, -21 }, { 107, 77, 14 }, { 467, 60, -69 }, { 485, 469, -74 },
            { 206, 276, 93 }, { 118, 62, 87 }, { 268, 16, -29 }, { 488, 498, 56 }, { 28, 217, 19 },
            { 170, 401, 6 }, { 18, 92, -30 }, { 356, 294, -90 }, { 309, 400, -19 },
            { 315, 455, -85 }, { 297, 334, 6 }, { 145, 443, 14 }, { 469, 363, -59 },
            { 395, 126, -24 }, { 299, 321, 12 }, { 59, 76, 51 }, { 307, 383, -22 },
            { 352, 217, 52 }, { 189, 199, 36 }, { 459, 328, -43 }, { 395, 308, 39 },
            { 292, 103, 84 }, { 241, 300, 47 }, { 53, 10, 10 }, { 202, 54, 19 }, { 181, 171, 17 },
            { 351, 268, 59 }, { 61, 101, 66 }, { 187, 436, -87 }, { 139, 450, -30 }, { 67, 8, 98 },
            { 368, 39, -5 }, { 446, 251, 56 }, { 56, 19, 23 }, { 91, 465, 91 }, { 146, 175, -50 },
            { 393, 406, 70 }, { 273, 352, -61 }, { 8, 166, 82 }, { 164, 25, -30 },
            { 334, 389, -57 }, { 5, 88, 86 }, { 171, 489, -98 }, { 334, 339, -52 },
            { 441, 92, -40 }, { 104, 335, 63 }, { 126, 467, -34 }, { 248, 352, -49 },
            { 452, 203, 98 }, { 166, 394, 68 }, { 223, 415, 62 }, { 383, 83, -49 },
            { 265, 489, -54 }, { 370, 30, -70 }, { 34, 386, 53 }, { 95, 435, -73 },
            { 236, 348, -69 }, { 332, 79, 9 }, { 481, 330, 16 }, { 480, 419, 92 }, { 59, 81, -15 },
            { 232, 183, 79 }, { 17, 476, -18 }, { 135, 17, 40 }, { 24, 107, 88 }, { 138, 355, 1 },
            { 89, 76, 64 }, { 100, 332, -49 }, { 228, 351, 65 }, { 252, 63, 51 }, { 23, 350, -97 },
            { 312, 108, -56 }, { 313, 491, 62 }, { 456, 332, 17 }, { 296, 317, 76 },
            { 115, 103, -32 }, { 279, 6, 15 }, { 452, 287, 92 }, { 411, 7, 55 }, { 65, 232, 0 },
            { 307, 143, -9 }, { 340, 34, -77 }, { 448, 209, 29 }, { 295, 401, -68 },
            { 305, 328, 42 }, { 337, 304, 31 }, { 8, 76, -100 }, { 153, 415, 36 }, { 180, 351, 41 },
            { 122, 191, -45 }, { 193, 372, 62 }, { 419, 160, 51 }, { 10, 472, 85 },
            { 177, 255, 42 }, { 165, 190, 59 }, { 406, 237, 29 }, { 353, 304, -2 },
            { 124, 218, -11 }, { 120, 196, -8 }, { 367, 312, -2 }, { 494, 102, -18 },
            { 31, 189, -63 }, { 9, 80, -93 }, { 17, 429, 59 }, { 290, 342, -90 }, { 22, 351, 53 },
            { 200, 111, -58 }, { 404, 93, -24 }, { 38, 401, -75 }, { 266, 119, -12 },
            { 463, 87, 33 }, { 91, 10, -94 }, { 49, 357, -2 }, { 327, 281, 90 }, { 414, 387, 53 },
            { 476, 51, -37 }, { 399, 135, -75 }, { 380, 273, 39 }, { 301, 0, 65 }, { 135, 495, 65 },
            { 270, 159, 99 }, { 369, 362, -81 }, { 171, 345, -71 }, { 183, 376, -91 },
            { 323, 60, 75 }, { 258, 227, -45 }, { 208, 222, -37 }, { 150, 494, -94 },
            { 228, 418, 60 }, { 427, 213, 41 }, { 198, 22, -40 }, { 381, 111, -66 },
            { 301, 394, -66 }, { 186, 270, 31 }, { 489, 174, -16 }, { 109, 422, -22 },
            { 121, 35, -5 }, { 481, 158, 49 }, { 221, 46, 48 }, { 198, 19, 52 }, { 429, 457, -20 },
            { 179, 350, 36 }, { 401, 241, 36 }, { 484, 136, 87 }, { 361, 112, -58 },
            { 194, 359, 70 }, { 327, 303, -28 }, { 480, 488, -93 }, { 120, 0, 60 },
            { 464, 206, 31 }, { 165, 134, 1 }, { 334, 65, 92 }, { 55, 20, 76 }, { 236, 28, 59 },
            { 216, 114, 28 }, { 459, 467, 84 }, { 363, 449, -78 }, { 268, 309, -16 },
            { 261, 294, -100 }, { 22, 157, -72 }, { 97, 142, -41 }, { 306, 487, 60 },
            { 218, 364, 60 }, { 196, 377, -3 }, { 379, 276, -78 }, { 410, 498, 92 },
            { 444, 70, 97 }, { 306, 475, 95 }, { 119, 473, 45 }, { 420, 416, -69 }, { 85, 414, 94 },
            { 376, 204, 93 }, { 273, 435, 100 }, { 481, 116, 92 }, { 300, 152, 99 },
            { 326, 209, 9 }, { 151, 292, -63 }, { 429, 181, -45 }, { 43, 497, 9 },
            { 321, 247, -81 }, { 83, 430, -39 }, { 471, 450, 27 }, { 234, 372, -56 },
            { 389, 207, 83 }, { 38, 67, 94 }, { 307, 313, -75 }, { 11, 165, 67 }, { 355, 450, 82 },
            { 412, 359, -73 }, { 221, 99, 63 }, };
        double maxWeight = 14655;
        double minWeight = -14892;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    /**
     * Random graph with 1500 vertices and 1500 edges
     */
    @Test
    public void testGetMatching19()
    {
        int[][] edges = new int[][] { { 678, 385, 85 }, { 786, 1109, -39 }, { 1164, 937, 24 },
            { 40, 365, -82 }, { 892, 879, 28 }, { 1284, 231, -61 }, { 812, 246, 42 },
            { 1337, 415, 80 }, { 1391, 369, 98 }, { 18, 1423, -98 }, { 241, 648, 82 },
            { 635, 1165, -12 }, { 384, 17, -22 }, { 1357, 849, -90 }, { 1111, 309, -98 },
            { 1233, 695, -52 }, { 189, 31, -62 }, { 232, 1138, -86 }, { 1200, 1141, -26 },
            { 702, 714, 79 }, { 753, 1313, 56 }, { 1024, 1414, -58 }, { 706, 151, -37 },
            { 1331, 1404, -74 }, { 1091, 1177, -30 }, { 296, 441, -40 }, { 886, 818, 16 },
            { 1476, 1316, 20 }, { 762, 880, -44 }, { 836, 1436, -63 }, { 541, 763, 91 },
            { 233, 62, 12 }, { 732, 874, -82 }, { 1192, 1475, 47 }, { 314, 224, -74 },
            { 1017, 737, 49 }, { 241, 1194, -50 }, { 1296, 1267, -80 }, { 1141, 349, -35 },
            { 660, 1207, 83 }, { 194, 1202, -14 }, { 1459, 1251, -6 }, { 1269, 1060, -34 },
            { 146, 1019, 35 }, { 1189, 893, -64 }, { 494, 993, 81 }, { 23, 1415, 72 },
            { 1435, 1113, -59 }, { 1254, 306, -92 }, { 1060, 240, -65 }, { 936, 247, -34 },
            { 1356, 1164, -33 }, { 446, 1054, -21 }, { 515, 617, 4 }, { 1093, 792, 7 },
            { 1351, 314, -89 }, { 1478, 422, 100 }, { 519, 929, -28 }, { 151, 598, 74 },
            { 672, 532, -65 }, { 1167, 293, -16 }, { 676, 687, -80 }, { 519, 1460, -72 },
            { 140, 186, 64 }, { 861, 430, -27 }, { 395, 37, 53 }, { 228, 257, 70 },
            { 867, 285, -7 }, { 81, 1404, -25 }, { 1293, 742, -17 }, { 738, 493, -87 },
            { 512, 710, -43 }, { 1301, 300, -19 }, { 881, 571, 100 }, { 599, 375, 81 },
            { 91, 216, 42 }, { 814, 1259, -1 }, { 957, 172, 8 }, { 723, 655, 43 }, { 460, 752, 98 },
            { 1471, 223, -43 }, { 482, 1150, -77 }, { 823, 899, -89 }, { 1046, 994, 80 },
            { 442, 325, -82 }, { 635, 1401, -34 }, { 756, 184, -65 }, { 27, 319, 33 },
            { 449, 94, 60 }, { 1144, 685, -65 }, { 1115, 396, -26 }, { 321, 995, -90 },
            { 174, 1112, -34 }, { 1073, 1279, -11 }, { 532, 1279, -84 }, { 85, 615, -31 },
            { 661, 1068, 35 }, { 235, 43, 71 }, { 1125, 37, -87 }, { 898, 514, 12 },
            { 1481, 840, -95 }, { 1239, 34, 69 }, { 1062, 924, -60 }, { 1361, 58, -95 },
            { 1019, 545, -18 }, { 1105, 495, 30 }, { 237, 652, 77 }, { 1024, 1358, -7 },
            { 1073, 1311, -37 }, { 689, 860, -34 }, { 1382, 637, 62 }, { 217, 1375, -41 },
            { 1359, 990, -16 }, { 797, 1468, -40 }, { 42, 1290, -89 }, { 43, 1133, 88 },
            { 1234, 1346, -90 }, { 1236, 1101, -94 }, { 345, 530, -57 }, { 253, 1281, -74 },
            { 770, 1228, 31 }, { 1182, 941, -20 }, { 707, 196, 47 }, { 172, 695, -65 },
            { 526, 1457, 46 }, { 895, 143, 3 }, { 1176, 57, 50 }, { 1171, 1036, 57 },
            { 1345, 420, -7 }, { 936, 589, 72 }, { 682, 1107, 84 }, { 339, 507, 97 },
            { 892, 914, -81 }, { 1447, 1438, 87 }, { 1261, 1073, -10 }, { 1255, 1069, 72 },
            { 273, 895, -95 }, { 798, 179, -88 }, { 1035, 836, -21 }, { 851, 1160, 48 },
            { 1364, 790, -21 }, { 1214, 912, 46 }, { 1092, 854, -70 }, { 1004, 1398, 87 },
            { 286, 1163, -78 }, { 385, 287, -90 }, { 656, 191, -67 }, { 1264, 1124, 15 },
            { 196, 1489, -26 }, { 1358, 401, 24 }, { 1202, 918, -65 }, { 1000, 175, -67 },
            { 23, 708, 33 }, { 1262, 1082, -72 }, { 701, 1135, -88 }, { 1355, 1307, -79 },
            { 808, 493, 91 }, { 859, 95, -84 }, { 272, 1441, 68 }, { 119, 557, 90 },
            { 1471, 735, 44 }, { 71, 888, -59 }, { 617, 735, -20 }, { 33, 1304, -17 },
            { 1346, 1190, -23 }, { 380, 562, 28 }, { 1064, 1185, -30 }, { 895, 146, 13 },
            { 101, 1465, 90 }, { 1048, 1200, -59 }, { 1191, 217, -66 }, { 128, 722, -46 },
            { 1198, 355, 71 }, { 708, 605, 75 }, { 97, 913, -20 }, { 464, 281, 71 },
            { 273, 219, 68 }, { 1314, 973, -2 }, { 1149, 990, 45 }, { 711, 1431, -76 },
            { 590, 1242, 98 }, { 621, 673, -11 }, { 746, 785, -28 }, { 428, 1129, 7 },
            { 1208, 606, -33 }, { 1091, 607, 0 }, { 1259, 196, 49 }, { 852, 355, 39 },
            { 994, 839, -13 }, { 1332, 1300, 8 }, { 951, 1231, 99 }, { 1031, 366, -44 },
            { 753, 1144, -54 }, { 863, 35, 27 }, { 340, 233, 37 }, { 1404, 489, -92 },
            { 564, 81, 37 }, { 1118, 971, -62 }, { 1118, 1386, -16 }, { 864, 838, -71 },
            { 161, 980, 48 }, { 755, 517, -59 }, { 863, 741, 90 }, { 793, 224, -76 },
            { 1007, 782, 96 }, { 463, 1257, -62 }, { 722, 306, 29 }, { 393, 708, -2 },
            { 1490, 1445, -56 }, { 697, 85, -91 }, { 818, 496, -87 }, { 34, 331, -28 },
            { 23, 746, -3 }, { 1298, 870, 23 }, { 782, 717, -10 }, { 278, 1352, -94 },
            { 1439, 574, 70 }, { 833, 400, 26 }, { 693, 1283, -89 }, { 26, 1480, 11 },
            { 939, 1428, 22 }, { 1298, 804, -58 }, { 1497, 1111, -74 }, { 397, 36, 69 },
            { 519, 663, -17 }, { 420, 1278, -3 }, { 874, 334, 17 }, { 565, 835, 73 },
            { 1344, 1418, -92 }, { 1090, 1271, -76 }, { 115, 1226, -20 }, { 826, 1047, -97 },
            { 796, 1286, 86 }, { 776, 171, 16 }, { 1482, 1004, -81 }, { 404, 303, 86 },
            { 72, 196, 11 }, { 1424, 146, 16 }, { 906, 373, 20 }, { 1203, 176, 54 },
            { 191, 49, 57 }, { 601, 524, 97 }, { 110, 595, -47 }, { 1003, 18, 79 },
            { 256, 720, -96 }, { 1044, 291, 46 }, { 1497, 1420, 81 }, { 440, 703, 32 },
            { 1182, 149, -63 }, { 1464, 1461, 25 }, { 661, 112, 14 }, { 126, 241, -84 },
            { 847, 378, 18 }, { 1125, 273, 33 }, { 543, 114, -1 }, { 1052, 521, -51 },
            { 479, 1192, 17 }, { 699, 1178, 17 }, { 824, 616, 60 }, { 206, 961, 48 },
            { 140, 613, 51 }, { 142, 992, 69 }, { 1471, 832, -60 }, { 1365, 1092, 15 },
            { 395, 877, -45 }, { 9, 120, 81 }, { 668, 644, -82 }, { 1132, 1138, 0 },
            { 788, 407, -66 }, { 846, 1127, -55 }, { 1009, 607, 91 }, { 191, 564, 61 },
            { 11, 356, -43 }, { 906, 580, -4 }, { 1089, 61, -97 }, { 538, 1074, 6 },
            { 1431, 36, -11 }, { 1096, 424, 98 }, { 426, 482, 57 }, { 924, 658, 23 },
            { 88, 18, -18 }, { 380, 1443, 73 }, { 1441, 587, -94 }, { 1247, 510, -100 },
            { 574, 891, -40 }, { 262, 791, 98 }, { 639, 1422, -69 }, { 1216, 128, 76 },
            { 231, 712, -72 }, { 539, 1249, 63 }, { 1212, 82, -51 }, { 1173, 871, 17 },
            { 1252, 1498, 66 }, { 1240, 1046, 40 }, { 415, 449, -96 }, { 182, 141, 86 },
            { 1032, 332, -66 }, { 1276, 442, 12 }, { 657, 1259, -35 }, { 533, 597, 70 },
            { 703, 1041, -81 }, { 941, 904, -89 }, { 7, 383, -63 }, { 1000, 636, -71 },
            { 1471, 804, -65 }, { 1144, 1423, -1 }, { 739, 85, 35 }, { 637, 159, -62 },
            { 1042, 683, -8 }, { 608, 337, -1 }, { 528, 337, -10 }, { 586, 845, 36 },
            { 121, 1449, -48 }, { 58, 77, -73 }, { 1228, 961, -62 }, { 136, 1311, -78 },
            { 93, 282, 48 }, { 112, 1020, -82 }, { 419, 837, 57 }, { 262, 1078, 7 },
            { 1450, 1122, 6 }, { 164, 1053, -36 }, { 180, 41, -84 }, { 1194, 1149, 58 },
            { 1130, 1218, -95 }, { 427, 1191, 65 }, { 825, 1007, -12 }, { 1092, 710, 50 },
            { 865, 1144, 28 }, { 13, 292, -19 }, { 802, 523, 100 }, { 780, 128, -60 },
            { 481, 1141, 28 }, { 466, 1138, -69 }, { 225, 1157, -71 }, { 694, 541, 18 },
            { 473, 987, 68 }, { 732, 307, 77 }, { 88, 1172, 12 }, { 1454, 851, 3 },
            { 964, 1299, -6 }, { 586, 483, 98 }, { 604, 75, -14 }, { 468, 1472, 73 },
            { 130, 1095, 76 }, { 1125, 1247, -67 }, { 531, 1333, 85 }, { 696, 1089, 54 },
            { 991, 1287, -55 }, { 123, 1242, 67 }, { 935, 507, 93 }, { 1141, 176, -12 },
            { 733, 170, 38 }, { 1414, 838, 34 }, { 483, 1226, -34 }, { 75, 1336, -35 },
            { 1076, 836, -54 }, { 668, 1073, 90 }, { 932, 1484, 99 }, { 295, 236, 58 },
            { 933, 659, -79 }, { 538, 1014, -57 }, { 570, 499, 17 }, { 928, 832, -25 },
            { 1134, 332, 39 }, { 363, 32, 51 }, { 1102, 806, -99 }, { 1417, 773, 62 },
            { 539, 1077, 81 }, { 933, 940, -21 }, { 621, 477, 30 }, { 256, 1312, 54 },
            { 189, 1106, 77 }, { 417, 965, -22 }, { 844, 399, -7 }, { 696, 668, 78 },
            { 1381, 1027, 57 }, { 1093, 1453, -14 }, { 544, 1456, -1 }, { 368, 831, 65 },
            { 8, 991, -86 }, { 663, 1156, -61 }, { 1049, 266, -65 }, { 457, 1147, -46 },
            { 790, 1488, 27 }, { 245, 1430, -15 }, { 262, 1486, 95 }, { 278, 283, -34 },
            { 309, 1300, -70 }, { 541, 451, -97 }, { 113, 43, 33 }, { 339, 770, -12 },
            { 429, 603, 1 }, { 1289, 1301, 41 }, { 581, 128, 89 }, { 149, 1156, 37 },
            { 95, 888, 11 }, { 426, 978, -21 }, { 1266, 320, 62 }, { 698, 1482, 48 },
            { 1037, 896, -54 }, { 931, 572, -28 }, { 1401, 808, 75 }, { 196, 853, 38 },
            { 362, 476, -38 }, { 641, 735, -12 }, { 283, 397, -77 }, { 241, 140, -52 },
            { 1456, 897, 84 }, { 822, 80, 51 }, { 45, 732, -47 }, { 286, 945, -92 },
            { 232, 1093, 91 }, { 485, 810, -48 }, { 547, 764, 33 }, { 698, 794, 17 },
            { 183, 861, 23 }, { 1266, 311, -70 }, { 771, 284, 47 }, { 1146, 1226, -31 },
            { 361, 1138, 23 }, { 244, 237, 4 }, { 1097, 1196, -94 }, { 193, 212, 48 },
            { 159, 1323, -85 }, { 817, 1460, 34 }, { 304, 1240, 74 }, { 267, 700, -21 },
            { 1375, 239, 69 }, { 331, 448, -3 }, { 157, 809, 96 }, { 1484, 1432, 73 },
            { 753, 386, -90 }, { 723, 609, 6 }, { 108, 1285, -27 }, { 40, 170, 5 },
            { 474, 1163, 67 }, { 1111, 361, -82 }, { 609, 1005, 70 }, { 31, 1249, 39 },
            { 123, 473, 97 }, { 825, 1127, -73 }, { 461, 647, 55 }, { 197, 1491, -62 },
            { 368, 177, -29 }, { 420, 368, 95 }, { 364, 1032, 52 }, { 201, 74, 87 },
            { 1391, 883, -18 }, { 432, 844, 55 }, { 384, 1469, -2 }, { 639, 1053, 26 },
            { 684, 1067, -58 }, { 1124, 192, 53 }, { 33, 340, -76 }, { 904, 614, -27 },
            { 1281, 1312, 11 }, { 558, 183, -10 }, { 589, 242, 68 }, { 686, 449, -19 },
            { 906, 1124, -34 }, { 100, 799, -88 }, { 1136, 496, -9 }, { 267, 1001, -78 },
            { 325, 638, 73 }, { 1223, 374, -79 }, { 75, 216, 54 }, { 1210, 76, -57 },
            { 901, 773, 91 }, { 866, 296, 99 }, { 394, 44, 67 }, { 539, 737, 5 }, { 960, 443, -61 },
            { 693, 978, 44 }, { 800, 1068, -30 }, { 1465, 573, 9 }, { 271, 979, -62 },
            { 952, 1147, 30 }, { 980, 1022, 52 }, { 184, 57, 9 }, { 1474, 340, 97 },
            { 851, 741, 28 }, { 124, 3, 43 }, { 1333, 1269, -4 }, { 615, 1114, 93 },
            { 610, 1459, 29 }, { 1148, 486, -57 }, { 172, 1145, 88 }, { 102, 916, 69 },
            { 333, 546, -77 }, { 674, 694, 50 }, { 231, 465, -37 }, { 1433, 972, -29 },
            { 679, 1037, -47 }, { 641, 490, 72 }, { 1496, 455, 74 }, { 40, 324, -46 },
            { 233, 236, 8 }, { 249, 758, 99 }, { 1437, 1497, 17 }, { 171, 1293, -38 },
            { 794, 411, 23 }, { 59, 753, -32 }, { 155, 1466, -49 }, { 737, 112, -87 },
            { 474, 402, 67 }, { 527, 247, -98 }, { 1070, 1252, 69 }, { 1181, 1047, -13 },
            { 949, 78, -17 }, { 332, 1035, -59 }, { 1289, 201, 33 }, { 145, 96, -87 },
            { 212, 599, -30 }, { 1132, 1236, 42 }, { 957, 725, 54 }, { 301, 959, 33 },
            { 281, 334, 33 }, { 822, 262, 7 }, { 81, 856, -8 }, { 547, 593, 95 },
            { 309, 1241, -10 }, { 1410, 1076, -76 }, { 1073, 466, 22 }, { 1423, 790, -78 },
            { 359, 521, -77 }, { 767, 50, -35 }, { 1197, 1441, -53 }, { 998, 536, 30 },
            { 864, 1017, 42 }, { 962, 182, 18 }, { 641, 979, -59 }, { 625, 1363, -95 },
            { 631, 122, 89 }, { 1407, 1184, 56 }, { 389, 643, 27 }, { 33, 1095, -99 },
            { 1493, 745, 36 }, { 149, 821, 87 }, { 377, 935, 30 }, { 418, 1386, 90 },
            { 896, 673, 29 }, { 166, 218, 80 }, { 700, 1345, -15 }, { 231, 433, 97 },
            { 1390, 896, 9 }, { 162, 131, 83 }, { 818, 925, 37 }, { 346, 166, 85 },
            { 100, 1425, 15 }, { 284, 948, -83 }, { 64, 415, -82 }, { 654, 226, 19 },
            { 74, 1309, -43 }, { 534, 913, 77 }, { 1001, 1319, -63 }, { 852, 1469, -98 },
            { 780, 1488, 53 }, { 719, 747, 72 }, { 1284, 1455, -46 }, { 23, 1215, 61 },
            { 685, 1355, 84 }, { 1162, 144, -34 }, { 591, 486, -52 }, { 790, 203, 51 },
            { 801, 1034, 48 }, { 126, 542, 9 }, { 1132, 1128, -62 }, { 116, 732, -43 },
            { 1028, 1045, 22 }, { 1094, 1040, 45 }, { 401, 379, -32 }, { 723, 811, 8 },
            { 1392, 901, -70 }, { 152, 139, -57 }, { 1019, 642, -5 }, { 1444, 717, -19 },
            { 341, 962, 45 }, { 1356, 305, -3 }, { 144, 489, -65 }, { 667, 1184, 62 },
            { 382, 1260, -93 }, { 645, 941, -51 }, { 936, 838, -6 }, { 1349, 272, -57 },
            { 1296, 477, 57 }, { 629, 416, -39 }, { 453, 205, -36 }, { 1420, 556, 95 },
            { 1038, 63, 54 }, { 859, 344, -11 }, { 784, 645, -8 }, { 1216, 916, -100 },
            { 842, 1037, -15 }, { 1414, 685, -6 }, { 1206, 1060, -8 }, { 1274, 954, -46 },
            { 809, 597, -100 }, { 788, 914, 31 }, { 1357, 1166, 84 }, { 1334, 408, 97 },
            { 1441, 917, -23 }, { 406, 774, 43 }, { 1238, 1490, 21 }, { 683, 1022, -54 },
            { 1189, 808, -99 }, { 306, 1446, 2 }, { 236, 1466, 35 }, { 612, 1463, -10 },
            { 637, 1044, 56 }, { 1470, 184, -55 }, { 1280, 922, -31 }, { 831, 1271, 58 },
            { 1320, 752, 69 }, { 937, 252, -39 }, { 629, 830, 34 }, { 439, 845, 84 },
            { 1028, 554, -55 }, { 699, 377, 87 }, { 1487, 991, -49 }, { 1140, 672, 81 },
            { 6, 451, -87 }, { 393, 1214, -2 }, { 110, 1008, 39 }, { 596, 615, 23 },
            { 1101, 1468, 35 }, { 664, 459, -89 }, { 218, 631, -42 }, { 605, 1335, -5 },
            { 42, 649, 35 }, { 1046, 4, -17 }, { 491, 615, -52 }, { 920, 926, 45 }, { 244, 94, 92 },
            { 1246, 1275, -47 }, { 1136, 62, 28 }, { 270, 372, 52 }, { 1119, 792, 89 },
            { 294, 1208, 94 }, { 954, 739, 4 }, { 448, 304, -76 }, { 538, 239, 75 },
            { 374, 154, -82 }, { 1148, 1075, -9 }, { 290, 914, -74 }, { 1264, 1160, 5 },
            { 1004, 509, -3 }, { 995, 1406, -12 }, { 117, 903, -48 }, { 473, 462, -44 },
            { 328, 1008, 5 }, { 274, 625, -70 }, { 674, 863, -87 }, { 11, 43, -47 },
            { 148, 547, -87 }, { 825, 959, -82 }, { 1335, 601, 40 }, { 645, 702, -15 },
            { 978, 1240, -8 }, { 779, 10, 56 }, { 892, 218, -85 }, { 1005, 373, 22 },
            { 971, 132, 36 }, { 506, 1185, -79 }, { 489, 438, 37 }, { 1295, 494, -35 },
            { 657, 909, 50 }, { 1460, 1466, 6 }, { 1073, 560, -34 }, { 1435, 436, 94 },
            { 366, 1339, -51 }, { 125, 800, 44 }, { 778, 986, 45 }, { 1081, 990, 64 },
            { 594, 1410, 3 }, { 362, 720, -19 }, { 344, 370, 99 }, { 409, 628, 31 },
            { 343, 1492, 26 }, { 199, 2, 6 }, { 385, 561, -35 }, { 951, 279, -36 },
            { 252, 334, -41 }, { 370, 207, -87 }, { 804, 520, 6 }, { 729, 1080, -94 },
            { 597, 486, 27 }, { 805, 994, 28 }, { 1186, 580, -86 }, { 971, 145, 40 },
            { 1072, 183, 27 }, { 1194, 125, 39 }, { 894, 860, 50 }, { 1352, 1142, -6 },
            { 751, 502, 95 }, { 1294, 1004, 20 }, { 273, 1248, 56 }, { 840, 351, -82 },
            { 67, 930, -21 }, { 689, 1030, -15 }, { 62, 1438, -14 }, { 1467, 137, -65 },
            { 1457, 641, -2 }, { 122, 1337, -68 }, { 48, 911, -2 }, { 525, 429, -38 },
            { 500, 68, 54 }, { 1382, 1477, -15 }, { 445, 588, -91 }, { 335, 417, -96 },
            { 65, 98, 17 }, { 324, 402, 19 }, { 1473, 1312, 32 }, { 1362, 1464, -48 },
            { 1324, 1334, -35 }, { 948, 953, 64 }, { 694, 419, -35 }, { 917, 1416, 76 },
            { 1065, 755, 70 }, { 1382, 1494, 82 }, { 1015, 378, -25 }, { 1493, 1084, -79 },
            { 8, 97, 82 }, { 346, 57, 17 }, { 987, 864, -60 }, { 589, 638, -31 }, { 691, 203, 55 },
            { 1363, 278, 46 }, { 389, 8, 80 }, { 774, 549, 97 }, { 1252, 741, 6 },
            { 1455, 1359, 65 }, { 1363, 206, 100 }, { 1238, 978, -47 }, { 815, 1030, -5 },
            { 664, 423, 24 }, { 854, 826, -85 }, { 710, 768, -42 }, { 887, 325, 31 },
            { 782, 815, -50 }, { 394, 1365, 50 }, { 1238, 1206, 17 }, { 702, 1070, -97 },
            { 570, 43, -23 }, { 384, 734, -4 }, { 1295, 57, -55 }, { 1279, 68, -53 },
            { 830, 1196, 18 }, { 1122, 1452, 42 }, { 18, 293, -76 }, { 297, 962, 76 },
            { 664, 1221, -4 }, { 648, 1434, 46 }, { 245, 656, -14 }, { 1236, 101, 19 },
            { 235, 732, -62 }, { 163, 718, -66 }, { 1103, 699, -25 }, { 1209, 1438, -54 },
            { 606, 1405, 29 }, { 836, 755, -50 }, { 573, 354, 71 }, { 1373, 790, -33 },
            { 738, 1244, -69 }, { 911, 1449, 0 }, { 77, 355, 97 }, { 1108, 1072, 6 },
            { 1355, 281, -8 }, { 138, 1363, 27 }, { 825, 1103, -26 }, { 356, 28, -9 },
            { 1024, 1389, -62 }, { 1142, 648, -99 }, { 431, 219, 34 }, { 830, 1072, -82 },
            { 485, 1440, 77 }, { 811, 553, -74 }, { 684, 519, 12 }, { 969, 444, -88 },
            { 922, 651, -94 }, { 1254, 1396, 48 }, { 592, 1334, -66 }, { 848, 600, 35 },
            { 1484, 325, 100 }, { 1416, 341, 77 }, { 1142, 1183, -75 }, { 819, 3, -38 },
            { 781, 196, -65 }, { 67, 562, -63 }, { 898, 44, 33 }, { 879, 527, 65 },
            { 994, 324, 40 }, { 462, 1176, -52 }, { 633, 1116, 8 }, { 240, 250, 48 },
            { 1403, 861, 33 }, { 63, 633, -76 }, { 1470, 1084, 40 }, { 1085, 149, -38 },
            { 415, 947, -40 }, { 730, 39, 11 }, { 745, 415, 97 }, { 1433, 1409, 13 },
            { 183, 667, -17 }, { 757, 1234, -74 }, { 877, 1136, 89 }, { 1213, 116, 20 },
            { 770, 529, 10 }, { 560, 884, 13 }, { 1084, 389, -16 }, { 1363, 1291, 95 },
            { 280, 418, -46 }, { 369, 910, -67 }, { 1047, 1243, 48 }, { 427, 544, 90 },
            { 1485, 570, -90 }, { 144, 269, -22 }, { 949, 1303, 84 }, { 473, 191, 76 },
            { 753, 645, 91 }, { 1189, 884, 23 }, { 399, 974, -32 }, { 120, 1175, -59 },
            { 455, 1395, -2 }, { 999, 1039, 73 }, { 431, 602, -61 }, { 1015, 604, -61 },
            { 197, 966, -26 }, { 57, 612, -1 }, { 1283, 97, -79 }, { 181, 1096, -66 },
            { 681, 1413, -67 }, { 841, 485, -42 }, { 926, 1031, 97 }, { 988, 1048, 64 },
            { 487, 37, -97 }, { 424, 1069, -28 }, { 1156, 717, -14 }, { 1464, 63, 65 },
            { 508, 1095, -42 }, { 789, 452, 3 }, { 696, 895, 26 }, { 79, 52, -64 },
            { 610, 445, 32 }, { 631, 1002, 24 }, { 1407, 181, -17 }, { 660, 982, 82 },
            { 963, 834, 5 }, { 930, 1044, 72 }, { 812, 803, -20 }, { 763, 705, -45 },
            { 534, 121, -88 }, { 676, 1021, -21 }, { 1072, 475, 61 }, { 505, 1201, -62 },
            { 962, 1131, 67 }, { 1063, 1033, 24 }, { 594, 1196, -22 }, { 974, 1488, 43 },
            { 1484, 700, -66 }, { 1215, 318, -85 }, { 3, 443, -74 }, { 1412, 1329, 82 },
            { 139, 1484, -84 }, { 67, 449, 1 }, { 440, 199, 65 }, { 1316, 1178, -51 },
            { 12, 1004, -14 }, { 1209, 415, -13 }, { 1232, 339, -9 }, { 1078, 228, -5 },
            { 631, 572, 60 }, { 805, 1103, 29 }, { 1305, 845, 30 }, { 1087, 287, -72 },
            { 166, 101, 95 }, { 53, 600, 88 }, { 1117, 851, 4 }, { 989, 1058, -16 },
            { 330, 115, 32 }, { 1064, 1106, -61 }, { 33, 1087, -70 }, { 635, 1470, 41 },
            { 160, 590, 45 }, { 749, 764, -54 }, { 112, 617, 64 }, { 952, 1077, -87 },
            { 1138, 1355, 64 }, { 887, 1157, -42 }, { 134, 666, -81 }, { 1311, 118, 34 },
            { 512, 121, 4 }, { 276, 1333, 87 }, { 1227, 553, -86 }, { 411, 1381, 75 },
            { 1396, 847, -92 }, { 85, 331, 7 }, { 780, 16, 37 }, { 1250, 1378, 91 },
            { 1219, 919, -89 }, { 1298, 1487, -37 }, { 150, 797, -6 }, { 936, 971, -36 },
            { 455, 1246, 0 }, { 33, 63, 50 }, { 1348, 663, 43 }, { 506, 1172, -54 },
            { 423, 833, 96 }, { 334, 1177, 93 }, { 1236, 877, -67 }, { 737, 265, -38 },
            { 347, 1328, -2 }, { 1182, 45, 19 }, { 1027, 212, -95 }, { 655, 1489, 0 },
            { 1283, 327, 78 }, { 53, 949, -34 }, { 484, 119, -52 }, { 35, 1391, -51 },
            { 527, 311, -64 }, { 354, 367, 3 }, { 1412, 361, 15 }, { 804, 398, -2 },
            { 378, 1372, 61 }, { 329, 163, 22 }, { 940, 707, 72 }, { 1229, 1435, -6 },
            { 937, 342, 24 }, { 490, 1112, 87 }, { 784, 1424, 22 }, { 1352, 880, -47 },
            { 451, 1286, 81 }, { 26, 850, -20 }, { 641, 235, -4 }, { 532, 572, -49 },
            { 681, 1016, 0 }, { 779, 447, 38 }, { 412, 426, 49 }, { 1037, 36, -15 },
            { 669, 973, -94 }, { 1218, 1428, 3 }, { 636, 767, -61 }, { 149, 1442, -87 },
            { 961, 469, 40 }, { 302, 1035, 44 }, { 791, 1081, -33 }, { 1039, 686, -29 },
            { 1404, 1296, 79 }, { 349, 565, -23 }, { 1345, 1050, 81 }, { 1174, 311, -81 },
            { 985, 859, 43 }, { 1428, 163, -43 }, { 438, 1048, 56 }, { 1344, 581, -98 },
            { 597, 706, -1 }, { 1344, 587, -100 }, { 1011, 838, 31 }, { 998, 291, 0 },
            { 331, 1157, -79 }, { 994, 1458, -54 }, { 910, 57, 44 }, { 225, 532, 70 },
            { 632, 725, -73 }, { 542, 146, -42 }, { 249, 1414, 36 }, { 1212, 660, -75 },
            { 623, 203, -33 }, { 969, 980, -35 }, { 166, 93, -48 }, { 67, 322, 54 },
            { 309, 238, -81 }, { 137, 861, 17 }, { 1414, 110, 60 }, { 279, 1081, -97 },
            { 1200, 686, 83 }, { 330, 667, 92 }, { 239, 714, 77 }, { 849, 834, 77 },
            { 441, 42, -93 }, { 744, 1250, 54 }, { 468, 628, 98 }, { 171, 1194, -70 },
            { 1020, 1475, -27 }, { 1226, 1002, 27 }, { 1306, 379, -21 }, { 1012, 534, -40 },
            { 1265, 1068, 36 }, { 411, 377, -66 }, { 655, 760, 25 }, { 1002, 1365, -17 },
            { 567, 1133, -2 }, { 1425, 619, -20 }, { 1498, 1127, -54 }, { 625, 31, -62 },
            { 643, 741, 4 }, { 449, 209, -55 }, { 1474, 977, 9 }, { 507, 1246, 21 },
            { 984, 1205, 93 }, { 142, 740, -58 }, { 428, 205, -8 }, { 295, 1322, 94 },
            { 934, 994, -53 }, { 1103, 136, -44 }, { 708, 1145, 16 }, { 1373, 291, -31 },
            { 1477, 976, -2 }, { 517, 381, -80 }, { 405, 283, 46 }, { 535, 587, -51 },
            { 396, 491, 86 }, { 1267, 726, -47 }, { 472, 923, -95 }, { 448, 475, 53 },
            { 525, 520, 61 }, { 1247, 1382, -64 }, { 1063, 1318, -48 }, { 1466, 9, 99 },
            { 630, 447, -83 }, { 269, 314, -78 }, { 241, 639, 2 }, { 1141, 458, 57 },
            { 1248, 1225, -15 }, { 460, 959, -16 }, { 1038, 960, -36 }, { 228, 1491, 31 },
            { 406, 1453, -41 }, { 1163, 950, -35 }, { 593, 184, -77 }, { 1493, 494, 67 },
            { 1309, 76, -56 }, { 955, 989, -67 }, { 1136, 952, 42 }, { 844, 480, 60 },
            { 448, 191, 21 }, { 49, 494, -92 }, { 1080, 1264, -48 }, { 1254, 294, -10 },
            { 818, 1486, 19 }, { 1267, 1, -74 }, { 704, 845, -18 }, { 660, 1255, -68 },
            { 1189, 457, -49 }, { 1256, 633, 42 }, { 397, 654, -78 }, { 344, 242, 36 },
            { 1007, 1201, -12 }, { 571, 261, -29 }, { 1034, 18, 96 }, { 1484, 143, 46 },
            { 57, 518, 81 }, { 1007, 133, 17 }, { 251, 522, -63 }, { 1432, 985, 27 },
            { 363, 1469, -14 }, { 230, 1260, 29 }, { 104, 1074, 85 }, { 755, 1379, -82 },
            { 535, 1365, -38 }, { 520, 434, -5 }, { 337, 1447, -13 }, { 203, 1416, 60 },
            { 568, 251, -55 }, { 750, 806, -52 }, { 841, 680, -66 }, { 1179, 1125, -71 },
            { 907, 892, -55 }, { 754, 862, -12 }, { 938, 171, -61 }, { 631, 468, 78 },
            { 905, 980, 69 }, { 332, 1200, -61 }, { 901, 1267, -54 }, { 172, 457, 80 },
            { 318, 636, -6 }, { 509, 189, -97 }, { 1364, 158, -40 }, { 279, 1200, 8 },
            { 1322, 1415, -59 }, { 234, 639, -5 }, { 1266, 246, 17 }, { 1225, 1151, 56 },
            { 1025, 74, 25 }, { 1328, 1186, -22 }, { 1287, 110, 10 }, { 42, 246, -97 },
            { 978, 857, 76 }, { 1143, 888, -52 }, { 651, 1028, 88 }, { 345, 540, 99 },
            { 722, 1061, -30 }, { 1436, 1107, 90 }, { 786, 1294, 7 }, { 748, 1373, -60 },
            { 1075, 1247, 63 }, { 917, 416, -72 }, { 979, 44, -24 }, { 422, 932, 9 },
            { 1251, 618, 29 }, { 1115, 516, 84 }, { 1340, 1491, 59 }, { 94, 304, -28 },
            { 997, 1339, 64 }, { 1117, 569, 74 }, { 642, 1105, 2 }, { 904, 1234, -21 },
            { 705, 570, 2 }, { 1365, 1036, -79 }, { 1376, 117, -39 }, { 557, 935, 51 },
            { 1247, 100, -11 }, { 1048, 202, -2 }, { 83, 350, -13 }, { 501, 705, 83 },
            { 166, 217, -3 }, { 855, 905, -39 }, { 600, 1182, 55 }, { 1487, 1425, -8 },
            { 851, 694, 86 }, { 1063, 126, -24 }, { 1055, 1302, -84 }, { 22, 1439, 34 },
            { 309, 82, 56 }, { 248, 1499, 63 }, { 869, 1102, 25 }, { 1356, 1180, -31 },
            { 765, 730, -26 }, { 763, 1433, -23 }, { 103, 388, -64 }, { 1272, 461, -38 },
            { 1001, 1164, 38 }, { 178, 349, 63 }, { 696, 1230, -63 }, { 121, 1143, 25 },
            { 1043, 1326, 49 }, { 909, 816, -43 }, { 497, 31, -41 }, { 303, 509, 44 },
            { 1349, 957, 9 }, { 853, 661, -24 }, { 857, 405, -10 }, { 99, 385, -1 },
            { 905, 1154, 30 }, { 1282, 1488, -74 }, { 765, 866, 47 }, { 741, 521, -49 },
            { 229, 777, 30 }, { 1295, 411, 62 }, { 523, 669, -67 }, { 1168, 554, 82 },
            { 1317, 434, -92 }, { 1435, 71, -19 }, { 505, 761, -97 }, { 1158, 657, -36 },
            { 490, 279, 65 }, { 1371, 1057, -90 }, { 664, 398, -30 }, { 1175, 1429, 11 },
            { 219, 754, -53 }, { 981, 1083, -13 }, { 684, 405, -88 }, { 1117, 156, 52 },
            { 132, 513, 15 }, { 573, 1367, 31 }, { 65, 479, 92 }, { 35, 976, 91 },
            { 301, 1088, 89 }, { 576, 730, -2 }, { 577, 834, -74 }, { 201, 54, -56 },
            { 671, 1340, -81 }, { 847, 1168, -2 }, { 1043, 437, -19 }, { 476, 138, -46 },
            { 72, 284, -52 }, { 1051, 1148, -58 }, { 1172, 143, -22 }, { 952, 235, 76 },
            { 1308, 1125, 56 }, { 1001, 134, -68 }, { 38, 122, -78 }, { 368, 818, -94 },
            { 596, 1152, -26 }, { 585, 1005, -31 }, { 607, 115, 80 }, { 278, 193, 78 },
            { 376, 156, -33 }, { 909, 1077, 9 }, { 1405, 327, -2 }, { 165, 168, -51 },
            { 371, 254, -2 }, { 1341, 1213, -91 }, { 238, 402, 89 }, { 925, 578, -40 },
            { 1164, 0, 81 }, { 883, 1232, 65 }, { 1087, 1243, -91 }, { 545, 678, 97 },
            { 685, 1124, -17 }, { 638, 17, 65 }, { 183, 649, -52 }, { 1278, 25, 1 },
            { 669, 915, -64 }, { 341, 45, -50 }, { 1091, 318, -76 }, { 608, 896, -92 },
            { 604, 582, -52 }, { 819, 1486, 53 }, { 317, 216, -85 }, { 1062, 1100, -24 },
            { 153, 53, -20 }, { 179, 160, -73 }, { 783, 970, 3 }, { 718, 1248, -60 },
            { 1061, 801, -30 }, { 1227, 562, -12 }, { 319, 1462, 25 }, { 21, 1360, 7 },
            { 1159, 1333, 71 }, { 511, 1240, 36 }, { 635, 647, -71 }, { 707, 526, -99 },
            { 535, 247, 10 }, { 1037, 316, 26 }, { 1237, 571, 16 }, { 49, 670, -85 },
            { 38, 838, 74 }, { 968, 487, 61 }, { 91, 1379, -73 }, { 509, 208, -44 },
            { 759, 79, -71 }, { 232, 1271, -81 }, { 461, 764, -47 }, { 1098, 462, 97 },
            { 1497, 495, -64 }, { 1442, 433, -74 }, { 503, 498, 83 }, { 335, 481, 50 },
            { 1009, 61, -14 }, { 703, 423, 32 }, { 559, 933, 60 }, { 1115, 1483, -91 },
            { 1127, 1202, -48 }, { 1452, 225, 72 }, { 473, 263, -20 }, { 273, 529, -31 },
            { 1395, 686, -84 }, { 421, 989, 36 }, { 1249, 782, 74 }, { 375, 388, -27 },
            { 915, 1047, 64 }, { 1011, 1109, 96 }, { 1319, 772, 55 }, { 564, 1014, -94 },
            { 1414, 1168, -100 }, { 1108, 470, 96 }, { 734, 1220, 93 }, { 956, 992, 0 },
            { 309, 1129, -79 }, { 1145, 257, 21 }, { 1483, 360, -12 }, { 637, 439, 71 },
            { 1165, 1451, -85 }, { 1145, 163, -11 }, { 945, 619, 100 }, { 1146, 254, 9 },
            { 190, 1006, 8 }, { 946, 1319, -8 }, { 169, 1315, 65 }, { 542, 864, 1 },
            { 948, 311, -70 }, { 702, 725, 12 }, { 910, 63, 83 }, { 1040, 905, 1 },
            { 979, 363, -54 }, { 756, 643, 83 }, { 1209, 1164, -84 }, { 430, 459, 44 },
            { 738, 32, -10 }, { 645, 1418, 98 }, { 1083, 169, 50 }, { 980, 895, 43 },
            { 373, 685, 38 }, { 363, 596, 6 }, { 535, 461, 31 }, { 849, 1296, -32 },
            { 589, 800, -48 }, { 747, 401, -6 }, { 396, 809, 20 }, { 1266, 721, -76 },
            { 1149, 820, -67 }, { 577, 1084, 24 }, { 325, 77, 6 }, { 252, 865, 73 },
            { 933, 655, -38 }, { 1013, 1018, -13 }, { 1050, 467, 59 }, { 717, 940, 86 },
            { 364, 262, -68 }, { 962, 307, -22 }, { 861, 1488, -33 }, { 1068, 97, 46 },
            { 892, 1310, -98 }, { 1164, 82, -23 }, { 730, 1488, -6 }, { 1112, 964, -21 },
            { 1071, 944, 14 }, { 483, 1384, -69 }, { 473, 257, -74 }, { 1439, 1456, 93 },
            { 310, 1410, 87 }, { 229, 866, -29 }, { 1199, 337, 56 }, { 1361, 1076, 19 },
            { 608, 483, 6 }, { 99, 765, -30 }, { 1481, 626, -90 }, { 1288, 116, -19 },
            { 726, 1314, -85 }, { 1224, 224, 6 }, { 1311, 1147, 14 }, { 448, 183, -59 },
            { 114, 779, -24 }, { 508, 1094, 12 }, { 1256, 3, 51 }, { 63, 1325, -22 },
            { 242, 1187, 52 }, { 357, 543, 36 }, { 541, 1247, -43 }, { 259, 944, 39 },
            { 92, 691, 84 }, { 481, 654, 47 }, { 697, 318, 10 }, { 833, 1421, 19 },
            { 733, 1418, 17 }, { 589, 1262, 59 }, { 764, 1478, 66 }, { 1491, 1182, -87 },
            { 1385, 701, -30 }, { 1302, 799, 98 }, { 135, 1170, -5 }, { 1467, 819, 56 },
            { 1448, 241, 23 }, { 616, 1232, 91 }, { 552, 149, -50 }, { 1157, 511, 70 },
            { 1080, 561, -61 }, { 937, 1065, 82 }, { 1237, 1260, -30 }, { 1263, 371, -57 },
            { 907, 259, 86 }, { 233, 1432, -98 }, { 647, 925, -52 }, { 620, 1324, -40 },
            { 877, 1186, 63 }, { 1370, 1062, -34 }, { 837, 760, -49 }, { 428, 1311, 98 },
            { 888, 428, 68 }, { 1311, 293, 62 }, { 332, 1479, -49 }, { 337, 770, -54 },
            { 221, 103, -70 }, { 1147, 1231, 53 }, { 219, 791, -73 }, { 142, 118, -69 },
            { 248, 609, 9 }, { 825, 683, 16 }, { 1407, 1380, 92 }, { 489, 1426, -15 },
            { 52, 43, 79 }, { 1104, 820, -18 }, { 446, 256, 40 }, { 530, 464, 88 },
            { 870, 1399, 1 }, { 134, 496, 64 }, { 982, 85, -49 }, { 356, 969, 65 },
            { 1134, 924, 51 }, { 1411, 23, -97 }, { 1497, 273, -56 }, { 37, 572, 62 },
            { 566, 1305, 17 }, { 81, 103, 76 }, { 1457, 452, -32 }, { 1252, 435, 15 },
            { 992, 1410, 92 }, { 711, 1417, 55 }, { 243, 90, 0 }, { 557, 199, -9 },
            { 747, 140, -77 }, { 1397, 1479, 29 }, { 1457, 1067, -68 }, { 934, 343, 42 },
            { 787, 696, 31 }, { 684, 1258, -100 }, { 546, 477, 36 }, { 449, 930, 41 },
            { 24, 13, -45 }, { 373, 651, 62 }, { 635, 463, 51 }, { 1267, 1216, 85 },
            { 53, 760, 42 }, { 325, 1068, 59 }, { 970, 910, 29 }, { 1297, 460, -2 },
            { 1182, 538, -11 }, { 1264, 790, -8 }, { 1446, 973, -2 }, { 98, 993, -18 },
            { 460, 191, -63 }, { 508, 87, -93 }, { 843, 427, 59 }, { 686, 383, -90 },
            { 55, 735, 53 }, { 425, 964, -58 }, { 443, 1186, -24 }, { 428, 961, -75 },
            { 1133, 1166, -12 }, { 928, 397, 33 }, { 766, 348, -94 }, { 1041, 714, -2 },
            { 1152, 473, 90 }, { 1251, 1154, 53 }, { 795, 1300, -37 }, { 1346, 1202, -75 },
            { 210, 513, 39 }, { 505, 875, 65 }, { 718, 1327, 65 }, { 792, 409, 99 },
            { 873, 69, -81 }, { 1080, 817, -71 }, { 345, 1109, -91 }, { 867, 885, 75 },
            { 1250, 262, -45 }, { 89, 474, -37 }, { 460, 1448, -94 }, { 782, 1454, 60 },
            { 140, 1497, 41 }, { 1297, 899, -40 }, { 550, 294, -66 }, { 1408, 1315, -66 },
            { 1404, 98, 31 }, { 1492, 821, -16 }, { 970, 1134, -22 }, { 743, 280, -5 },
            { 536, 717, 49 }, { 803, 1127, 48 }, { 427, 437, 52 }, { 1418, 460, -20 },
            { 124, 518, 36 }, { 32, 1432, 36 }, { 814, 1006, 87 }, { 1320, 1195, -58 },
            { 1478, 190, 70 }, { 1159, 528, -28 }, { 647, 349, -93 }, { 521, 967, 60 },
            { 491, 250, 31 }, { 1101, 802, 1 }, { 588, 446, 92 }, { 90, 525, 76 }, { 383, 173, 59 },
            { 1446, 717, 28 }, { 11, 1320, 84 }, { 1184, 1219, -78 }, { 625, 1037, -16 },
            { 601, 390, -100 }, { 783, 535, -72 }, { 155, 746, -41 }, { 1042, 501, 60 },
            { 981, 185, 60 }, { 252, 143, -3 }, { 1157, 1051, -78 }, { 426, 533, 92 },
            { 351, 870, 97 }, { 226, 884, 95 }, { 1319, 1196, 45 }, { 1327, 303, -69 },
            { 177, 820, 94 }, { 77, 1396, 93 }, { 1040, 646, 100 }, { 135, 219, 92 },
            { 1223, 1030, 99 }, { 1215, 957, 9 }, { 255, 902, -63 }, { 289, 1172, -45 },
            { 259, 924, 9 }, { 427, 1002, -81 }, { 523, 715, -39 }, { 513, 1184, 27 },
            { 1348, 1180, -56 }, { 695, 16, 83 }, { 1184, 368, 94 }, { 1330, 302, -75 },
            { 320, 1272, 67 }, { 263, 480, 82 }, { 295, 820, -73 }, { 577, 27, 63 }, };
        double maxWeight = 23875;
        double minWeight = -24426;
        test(edges, objectiveSense == MAXIMIZE ? maxWeight : minWeight, objectiveSense);
    }

    private void test(int[][] edges, double result, ObjectiveSense objectiveSense)
    {
        DefaultUndirectedGraph<Integer, DefaultEdge> graph =
            (DefaultUndirectedGraph<Integer, DefaultEdge>) TestUtil.createUndirected(edges);
        int maxVertex = 0;
        for (int[] edge : edges) {
            maxVertex = Math.max(Math.max(maxVertex, edge[0]), edge[1]);
        }
        graph.setVertexSupplier(SupplierUtil.createIntegerSupplier(maxVertex + 1));
        KolmogorovWeightedMatching<Integer, DefaultEdge> weightedMatching =
            new KolmogorovWeightedMatching<>(graph, options, objectiveSense);
        MatchingAlgorithm.Matching<Integer, DefaultEdge> matching = weightedMatching.getMatching();
        assertEquals(matching.getWeight(), result, EPS);
        assertTrue(weightedMatching.testOptimality());
        assertTrue(weightedMatching.getError() < EPS);
    }

}
