import java.io.*;
import java.util.*;

class Proj6
{

	public static void main(String[] args) throws IOException
	{
		List number = new LinkedList();
		List capacity = new LinkedList();
		System.out.println("My name is: Thomas Pitts");
		
		
		// get trials from file to lists
		try {
			BufferedReader in = new BufferedReader(new FileReader(args[0]));
			String line = in.readLine();
			while (line != null) {
			
			StringTokenizer tok= new StringTokenizer(line);
			number.add(Integer.valueOf(tok.nextToken()));
			capacity.add(Integer.valueOf(tok.nextToken()));
			line=in.readLine();
			}
		} catch(IOException e) {
			e.printStackTrace();
			System.exit(1);
		}

		// iterate through the trials
		Iterator numIter = number.iterator();
		Iterator capIter = capacity.iterator();
		int count=1;
		while (numIter.hasNext()) {
        int n=((Integer)numIter.next()).intValue();
				int c=((Integer)capIter.next()).intValue();
				System.out.println("Output for the case "+count+" (n="+n+", m="+c+"):");
				int paths = findPath(n,c);
				count++;
				System.out.println();System.out.println();
    }

	}  //end main

	
	public static int findPath(int n, int m)
	{
		LinkedList open = new LinkedList();
		GSNode found = null;
		int founds=0;
		
		GSNode root=new GSNode(n,null);
		
		open.add(root);
		root=null;
		
		int southC=0;
		int northC=0;
		int northM=0;
		int southM=0;
		while (!open.isEmpty()) {
			GSNode current = (GSNode)open.removeLast();
			//System.out.println("In While Loop: openSize="+open.size()+" closedSize="+closed.size());
			
			int cannibs=-1;
			int missions=-1;
			if (current.next == 's') {
				cannibs = current.northC;
				missions = current.northM;
			} else if (current.next == 'n') {
				cannibs = current.southC;
				missions = current.southM;
			}				
			cannibs = (cannibs > m) ? m : cannibs;
			missions = (missions > m) ? m : missions;


			//System.out.println("missions:= "+missions+" cannibs:="+cannibs);
			// for all valid boat moves
			for (int i=0; i <= cannibs; i++) 
				for (int j=0; j <= missions; j++) {
					boolean thisFound=false;
					// if move can fit on 'boat'
					if ((i + j <= m) && (i + j > 0)) {

						// if on north shore
						if (current.next == 's') {
							//System.out.println("	Currently on the north");
							southC=current.southC + i;
							southM=current.southM + j;
							northC=current.northC - i;
							northM=current.northM - j;
						} else if (current.next == 'n') {
							//System.out.println("	Currently on the south");
							southC=current.southC - i;
							southM=current.southM - j;
							northC=current.northC + i;
							northM=current.northM + j;
						}
						//System.out.println("(south "+current.southM+"M "+current.southC+"C - north "+current.northM+"M, "+current.northC+"C)");
						if (southM == 0 && southC == 0) {
							if (founds ==0)
								found = new GSNode(northM,northC,southM,southC,'s',current);
							founds++;
							thisFound=true;
						}
						
						if (!thisFound) {
						// if missionaries will not get eaten by cannibals
						if (((southM >= southC) || (southM == 0)) && ((northM >= northC) || (northM == 0))) 	{
							//System.out.println("	Passed bloody check");
							GSNode exp=null;
							if (current.next == 's')
								exp = new GSNode(northM,northC,southM,southC,'n',current);
							else if (current.next == 'n')
								exp = new GSNode(northM,northC,southM,southC,'s',current);
							
							if (!checkClosed(exp)) {
								//System.out.print("		Found a valid move: ");
								//System.out.println("(south "+southM+"M "+southC+"C - north "+northM+"M, "+northC+"C)");
							  
								open.addLast(exp);
							}
						
						}
						}
					}
				}
		}
		System.out.println("Number of different plans: "+founds);
		System.out.println();
		if (founds > 0)
			printPath(found);
		return founds;
	}

	
	public static boolean checkClosed(GSNode exp)
	{
		GSNode curr=exp.parent;
		while (curr != null) {
			if (exp.equiv(curr))
				return true;
			curr=curr.parent;
			//System.out.println("In Closed While");
		}
		return false;
	}

	public static void printPath(GSNode path)
	{
		if (path.parent != null)
			printPath(path.parent);
		
		System.out.print("(south "+path.southM+"M "+path.southC+"C - north "+path.northM+"M, "+path.northC+"C,");
		System.out.print(" boat at ");

		if (path.next=='s') {
			System.out.println("north) ");
		} else if (path.next=='n') {
			System.out.println("south) ");
		}
	}


} // end class Proj6