1989 ACM East Central Regional Programming Contest

Problem 4: Representation of Graph-Theoretic Trees

In this problem, we are considering graph-theoretic trees of n nodes. In computer science, the left/right order of the children of a node often matters; in graph theoretic trees it does not. Thus, all drawings in figure 1 illustrate the same labeled tree. On the other hand, the trees of figure 2 are all distinct.


FIGURE 1: All these trees are the same

FIGURE 2: All these trees are different

A theorem by Cayley states that the number of labeled trees is nn-2. Prufer gave a constructive proof of this theorem, whose main idea is as follows. Establish a one-to-one correspondence between the labeled trees and (n-2)-long sequences of numbers from the set [ 1, 2, ..., n ]. Since each element of the sequence can be any number from the set, it follows that the number of trees is nn-2. The next paragraph describes how a unique (n-2)-long sequence is constructed from the given tree.

Find the leaf node with the smallest label. Call it u. Let (u, v) be the edge connecting u with its only adjacent node v in the tree. Delete this edge; i.e., delete the node u, and 'erase' the line connecting u to v. Record v as the next element in the sequence we are construction. Repeat this process on the remaining tree until only two nodes are left. (Clearly, the original tree should have at least 2 nodes.) This process is illustrated below.

In this problem, you will reverse the process. Your task is to discover and program an algorithm to construct the tree, given the (n-2)-long sequence. Assume that n will be at most 256. Input file contains a number of sequences. Each sequence is a blank-separated list of numbers. A zero is used as the end of that sequence. A minus one (-1) is used as an explicit end of file. You should output the tree as a list of edges.

Sample Input

  3 3 2 2 3 2 9 0
  -1

Sample Output

  (1, 3)
  (4, 3)
  (5, 2)
  (6, 2)
  (7, 3)
  (3, 2)
  (2, 9)
  (8, 9)