import java.util.*;
 
class Variant {
 
	static Vector<Variant> variants;
	Vector<Variant> successors;
 
	int m_a;
	int m_b;
	int c_a;
	int c_b;
	boolean boat;
 
	Variant(int m_a, int c_a, int m_b, int c_b, boolean boat) {
		this.m_a = m_a;
		this.m_b = m_b;
		this.c_a = c_a;
		this.c_b = c_b;
		this.boat = boat;
		this.successors = new Vector<Variant>();
		variants.add(this);
		int s = (boat == false) ? -1 : 1;
		negotiate_successor(m_a + s*2, c_a + s*0, m_b - s*2, c_b - s*0, !boat);
		negotiate_successor(m_a + s*1, c_a + s*0, m_b - s*1, c_b - s*0, !boat);
		negotiate_successor(m_a + s*1, c_a + s*1, m_b - s*1, c_b - s*1, !boat);
		negotiate_successor(m_a + s*0, c_a + s*1, m_b - s*0, c_b - s*1, !boat);
		negotiate_successor(m_a + s*0, c_a + s*2, m_b - s*0, c_b - s*2, !boat);
	}
 
	void negotiate_successor(int m_a, int c_a, int m_b, int c_b, boolean boat) {
		if ((m_a > 0 && m_a < c_a) ||
			(m_b > 0 && m_b < c_b) ||
			m_a < 0 || m_b < 0 || c_a < 0 || c_b < 0)
			return;
		Variant v = Variant.exists(m_a, c_a, m_b, c_b, boat);
		if (v == null)
			v = new Variant(m_a, c_a, m_b, c_b, boat);
		this.successors.add(v);
 
	}
 
	boolean equals(int m_a, int c_a, int m_b, int c_b, boolean boat) {
		return (this.m_a == m_a && this.m_b == m_b && this.c_a == c_a && this.c_b == c_b && this.boat == boat);
	}
 
	boolean equals(Variant v) {
		return this.equals(v.m_a, v.c_a, v.m_b, v.c_b, v.boat);
	}
 
	boolean is_solved() {
		return (this.m_b == Game.MISSIONARIES && this.c_b == Game.CANNIBALS && this.boat == true);
	}
 
	static Variant exists(int m_a, int c_a, int m_b, int c_b, boolean boat) {
		Enumeration i = Variant.variants.elements();
		while(i.hasMoreElements()) {
			Variant v = (Variant)(i.nextElement());
			if (v.equals(m_a,c_a,m_b,c_b,boat))
				return v;
		}
		return null;
	}
 
	static void list_variants() {
		System.out.println(Variant.variants.size() + " variants total:");
		Enumeration i = Variant.variants.elements();
		while(i.hasMoreElements())
			((Variant)(i.nextElement())).info();
	}
 
	void info() {
		System.out.println("[" + this.m_a + " " + this.c_a + " " + this.m_b + " " + this.c_b + " " + this.boat + "]");
	}
 
}
 
class Path {
 
	static Vector<Path> paths;
	Vector<Variant> path;
	boolean block;
 
	Path(Variant v, Path p) {
 
		block = false;
 
		if (p != null)
			this.path = (Vector)(p.path.clone());
		else
			this.path = new Vector<Variant>();
 
		if (!this.has_variant(v))
			path.add(v);
		else block = true;
 
	}
 
	void info() {
		System.out.println("Path (number of elements: " + (path.size()-1) + ")");
		Enumeration e = path.elements();
		while (e.hasMoreElements())
			((Variant)(e.nextElement())).info();
	}
 
	boolean has_variant(Variant v) {
		Enumeration i = path.elements();
		while (i.hasMoreElements())
			if (((Variant)(i.nextElement())).equals(v))
				return true;
		return false;
	}
 
	void probe() {
		Variant v = path.lastElement();
		if (v.is_solved())
		{
			System.out.print("Found valid ");
			info();
		}
 
		if (this.block)
			return;
 
		else {
			Enumeration i = v.successors.elements();
			while(i.hasMoreElements()) {
				Path p = null;
				p = new Path((Variant)(i.nextElement()), this);
				if (p != null)
					Path.paths.add(p);
			}
		}
 
	}
 
}
 
public class Game {
 
	public static final int MISSIONARIES = 3;
	public static final int CANNIBALS    = 3;
 
	public static void main(String[] args) {
		Path.paths = new Vector<Path>();
		Variant.variants = new Vector<Variant>();
		Variant top = new Variant(3,3,0,0,false);
		Variant.list_variants();
		Path.paths.add(new Path(top, null));
		Enumeration e = Path.paths.elements();
		while (e.hasMoreElements())
			((Path)(e.nextElement())).probe();
 
	}
 
}