/**
 * Solving concentric mazes by converting them to graphs and doing
 * breadth-first search.
 *
 * Data structures, assignment 5
 * 0440949 Andreas van Cranenburgh <andreas@unstable.nl>
 *
 * Code for breadth-first search taken (with trivial modifications) from
 * Koffman and Wolfgang, Objects, Abstraction, Datastructures and Design using
 * Java, Ch. 12.
 * http://bcs.wiley.com/he-bcs/Books?action=resource&bcsId=2200&itemId=0471692646&resourceId=4634
 *
 * Quote from the assignment:
 *  Detailed description of input
 *  The first line will contain a single integer, n, the number of rings. The
 *  next n lines will contain pairs of integers, each pair will be the boundary
 *  of the doors.
 *  The next n-1 lines will contain integers that specify the position of the
 *  walls.  For the above example the input file is as follows:
 * 
 *  4
 *  85 95
 *  26 40 120 130 198 215 305 319
 *  67 90 161 180 243 256 342 360
 *  251 288
 *  45 135 300
 *  0 100 225 270
 *  65 180
 *
 * 	Example execution: (using the example above)
 * $ java Maze < maze.txt
 * The maze represented as graph:
 * 0: [2]
 * 1: [4, 5]
 * 2: [0, 3, 6]
 * 3: [2, 6]
 * 4: [1, 8]
 * 5: [1, 6]
 * 6: [2, 3, 5]
 * 7: [8, 9]
 * 8: [4, 7, 9]
 * 9: [7, 8]
 *
 * The Shortest path is:
 * [9, 8, 4, 1, 5, 6, 2, 0]
 *
 * */
    
import java.util.*;

public class Maze {
	public static final void main(String[] args) {
		/* parse standard input, return as graph */
		Graph m = readMaze(System.in);

		/* show the resulting graph */
		System.out.println("The maze represented as graph:");
		System.out.println(m);
		//System.out.println(m.getNumE());

		// Perform breadth-first search.
		int parent[] = BreadthFirstSearch.breadthFirstSearch(m, 0);

		// Construct the path.
		Stack<Integer> path = new Stack<Integer>();
		int v = m.vertices.size() - 1;
		while (parent[v] != -1) {
			path.push(new Integer(v));
			v = parent[v];
		}

		// start is always the start:
		path.push(0);
		Collections.reverse(path);

		// Output the path.
		System.out.println("The Shortest path is:");
		System.out.println(path);
	}
	
	/** Given a stream describing a concentric maze, produce a graph object
	 **/
	public static final Graph readMaze(java.io.InputStream in) {
		int n, first, last;
		Graph m = new Graph();

		/* scan the input for maze data */
		Scanner sc = new Scanner(in);

		/* number of rings */
		if (sc.hasNextInt())
			n = sc.nextInt();
		else
			return m;	/* fail on emtpy input */
			
		/* get positions of doors */
		for (int a = 0; a <= n; a++) {
			Scanner ring = new Scanner(sc.nextLine());
			while(ring.hasNextInt()) {
				int b = ring.nextInt();
				int c = ring.nextInt();
				m.add(new Vertex(a, b, c));
			}
		}

		/* get positions of walls */
		for (int a = 1; a < n; a++) {
			Scanner ring = new Scanner(sc.nextLine());
			if (ring.hasNextInt()) {
				first = ring.nextInt();
				last = first;
			} else
				break;
			while(ring.hasNextInt()) {
				int b = ring.nextInt();
				inferEdges(m, a, last, b);
				last = b;
			}
			inferEdges(m, a, last, first);
		}

		return m;
	}
	
	/** Given a pair of walls, find all vertices within those walls, and
	  * interconnect them.
	  * */
	static void inferEdges(Graph m, int ring, int wall1, int wall2) {
		java.util.List<Vertex> adjacentDoors = new java.util.Vector<Vertex>(); 
		for (int c = 0; c < m.vertices.size(); c++) {
			if (m.get(c).ring == ring || m.get(c).ring == ring + 1) {
				int l = m.get(c).left;
				int r = m.get(c).right;
				int w1 = wall1; 
				int w2 = wall2;
				/* The following four lines are necessary to compensate for
				 * degrees wrapping around.
				 * If two values are to be compared with a zero-crossing
				 * then compensate by adding 360 to the smaller one. */
				w1 = w1 > w2 && r >= 180 && w1 < 180 ? 360 + w1 : w1;
				w2 = wall1 > w2 && r >= 180 && w2 < 180 ? 360 + w2 : w2;
				l = wall1 > wall2 && l < 180 && wall1 >= 180 ? 360 + l : l;
				r = wall1 > wall2 && r < 180 && wall2 >= 180 ? 360 + r : r;
				if (w1 <= l && r <= w2) {
					/* connect this door with all previously seen doors
					(cartesian product minus reflexive links) */
					for (int d = 0; d < adjacentDoors.size(); d++) {
						m.get(c).add(adjacentDoors.get(d));
						adjacentDoors.get(d).add(m.get(c));
					}
					adjacentDoors.add(m.get(c));
				}
			}
		}
	}
}