== Enumerating trees We're used to thinking about rooted trees in computer science, but now for a while we'll be talking about *un*rooted trees. An unrooted tree is simply a graph with N nodes and N-1 edges, without cycles. Each node is reachable from any other node through exactly one simple path. Here's an example tree with three nodes. 1--2--3 a tree with a line shape In order to talk about different trees, we employ a traversal representation that looks like this: 1-2-3-2 traversal representation This can be thought of as the sequence of nodes encountered when tracing around the tree (say) clockwise. In the above case, we start at node 1, continue to node 2, turn at node 3, find node 2 again, and then we're back at node 1 (which we don't include at the end). The traversal representation is simply a way to identify each graph by its structure. For simplicity's sake, let the traversal representation be "canonical", in the sense that it always introduces previously unseen nodes with the numbers 1..*, in order. This reflects the fact that we're really dealing with unlabeled trees, and don't consider nodes to be distinct. Note that starting from a different node, or mirroring the tree in the plane that embeds it, may yield a different canonical traversal representation. (So it's not quite canonical.) You're free to pick any one of these if there are several. There's only one tree each with 1, 2, or 3 nodes. 4 is the first interesting case, and has two unique trees 1--2--3--4 another line 1-2-3-4-3-2 1--2--3 | a T-shape 1-2-3-2-4-2 4 Similarly, there are three unique trees with 5 nodes. Write a program that accepts a positive integer N on the command line, and outputs all unique unrooted unlabeled trees with N nodes, using canonical traversal representation. For example, for N = 4, the program should output the above two trees: 1-2-3-4-3-2 1-2-3-2-4-2