#include <list>
#include <algorithm>
#include <iostream>
#include <boost/foreach.hpp>

using namespace std;

list<int> get_branches(int root);

list<list<int> > get_all_paths(int root)
{
	list<int> branches;
	list<list<int> > allpaths;
	branches = get_branches(root);
	if (branches.empty()) {
		list<int> v(1, root);
		allpaths.push_back(v);
		return allpaths;
	}
	BOOST_FOREACH(int b, branches) {
		list<list<int> > partial_paths;
		partial_paths = get_all_paths(b);
		BOOST_FOREACH(list<int> partial_path, partial_paths) {
			partial_path.push_front(root);
			allpaths.push_back(partial_path);
		}
	}
	return allpaths;
}

/*
Graph generated by get_branches
#    1
#   / \
#  2   3
# / \
#4   5 
*/
list<int> get_branches(int root)
{
	if (root == 1) {
		int v[] = {2, 3};
		list<int> b(v, v+2);
		return b;
	}
	if (root == 2) {
		int v[] = {4, 5};
		list<int> b(v, v+2);
		return b;
	}
	list<int> b;
	return b;
}

void print_paths(const list<list<int> >& vv)
{
	BOOST_FOREACH(list<int> v, vv) {	
		BOOST_FOREACH(int i, v) {	
			cout<<i<<" ";
		}
		cout<<"\n";
	}
}

int main()
{
	int root;
	list<list<int> > vv;

	root = 1;
	vv = get_all_paths(root);
	print_paths(vv);
	return 0;
}