Chef at the River

Chef and $N$ animals (numbered $1$ through $N$) must cross a river. They are all currently located at the left bank; Chef wants all animals and himself to be located at the right bank at the end. Some of the animals do not get along with each other, so they must not be left unattended by Chef at the same bank at any point in time. These restrictions are described by a tree with $N$ vertices; an