import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Scanner;

/**
 * Satisfies Problem 19.e from Homework 1. Quoted from the homework:
 * <p>
 * Check whether a given comparator network is a sorting
 * network. The program reads a linear representation (not
 * necessarily canonical) on standard input. The output is a
 * single character, 1 if the input is a sorting network and 0
 * otherwise, followed by a single newline.  Explain, as
 * precisely as possible, why your program is correct. Include
 * this explanation as part of your Javadoc documentation, as
 * described below.
 * @author Ed
 */
public class CnetCheckSortMain {
    /**
     * Takes in the comparator network from stdin, creates a data set of the
     * proper size and configuration (a reverse sorted list of the same size
     * as the number of comparators, i.e., if there are comparators numbered
     * 0 to 5, the list will be {5, 4, ..., 1, 0} ). Applies the comparator
     * network to this reverse-sorted list, then checks the list for being
     * sorted correctly. Outputs 0 to stdout if list is not correctly sorted.
     * Outputs 1 if list is correctly sorted. Unlike other programs, you can
     * have as many comparators as you want in this one (since we aren't
     * dealing with graphics, I didn't need to restrict it to
     *
     * @param args      The command line arguments for the program. Are ignored
     *                  by this program.
     */
    public static void main(String[] args)
    {
        String input = "";

        System.out.println("Enter below a whitespace-delineated list of");
        System.out.println("integers that will serve as the basis for the");
        System.out.println("comparator network this program will use.");
        System.out.println("Enter the character X on a new line to stop");
        System.out.println("reading from standard output. No error handling");
        System.out.println("is done in the case of garbage characters, so");
        System.out.println("proof your own values.");
        System.out.println();

        Boolean breakLoop = false;

        Scanner s = new Scanner(System.in);

        // read from stdin, emerge on X or x
        while (breakLoop == false)
        {
            System.out.print("> ");
            String foo = s.nextLine().trim();

            if (foo.length() < 1) continue;

            if (foo.charAt(0) == 'X' || foo.charAt(0) == 'x')
            {
                breakLoop = true;
                continue;
            }
            else
            {
                input += foo + " ";
            }
        }

        input = input.trim();

        StringTokenizer st = new StringTokenizer(input);

        if (st.countTokens() % 2 == 1)
        {
            System.err.println("ERROR: Invalid input - odd number of tokens.");
            System.exit(1);
        }

        int numberOfComparators = -1;

        ArrayList<ComparatorPair> comparatorList =
                new ArrayList<ComparatorPair>();

        while (st.hasMoreTokens())
        {
            int x = Integer.parseInt(st.nextToken());
            if (x > numberOfComparators) numberOfComparators = x;

            int y = Integer.parseInt(st.nextToken());
            if (y > numberOfComparators) numberOfComparators = y;

            comparatorList.add(new ComparatorPair(x, y));
        }

        Integer[] dataArray = new Integer[numberOfComparators + 1];

        System.out.println();

        for (int i = 0; i < dataArray.length; i++)
        {
            dataArray[i] = numberOfComparators - i;
        }

        for(int i = 0; i < comparatorList.size(); i++)
        {
            ComparatorPair c = comparatorList.get(i);

            // not the most elegant swap ever, but it works

            int x = dataArray[c.left()];
            int y = dataArray[c.right()];
            int w;
            if (x > y)
            {
                w = y;
                y = x;
                x = w;
            }

            dataArray[c.left()] = x;
            dataArray[c.right()] = y;
        }

        for (int i = 1; i < dataArray.length; i++)
        {
            if ((dataArray[i] > dataArray[i - 1]) == false)
            {
                System.out.println("0");
                System.exit(0);
            }
        }
        System.out.println("1");
        System.exit(0);

        
    }
}