Given a Tree generate its Prüfer Code In graph-theory a Prüfer code is a unique sequence of integers that denotes a specific tree.

You can find the Prüfer code of a tree with the following algorithm taken from Wikipedia:


  Consider a labeled tree T with vertices {1, 2, ..., n}. At step i, remove the leaf with the smallest label and set the ith element of the Prüfer sequence to be the label of this leaf's neighbor.


(Note that since it's a leaf it will only have one neighbor).

You should stop the iteration when only two vertices remain in the graph.

Task

Given a labeled tree as input output its Prüfer code.  You may take input in any reasonable manner.  Such as an adjacency matrix or your languages builtin graph representation. (You may not take input as a Prüfer code).

This is code-golf so you should aim to minimize the bytes in your source.

Test cases

Here are some inputs in ASCII with their outputs below.  You do not need to support ASCII input like this.

    3
    |
1---2---4---6
    |
    5

{2,2,2,4}




1---4---3
    |
5---2---6---7
|
8

{4,4,2,6,2,5}




5---1---4   6
    |       |
    2---7---3

{1,1,2,7,3}
Mathematica, 34 bytes

&lt;&lt;Combinatorica`
LabeledTreeToCode


Somebody had to do it....

After loading the Combinatorica package, the function LabeledTreeToCode expects a tree input as an undirected graph with explicitly listed edges and vertices; for example, the input in the second test case could be Graph[{{{1, 4}}, {{4, 3}}, {{4, 2}}, {{2, 5}}, {{2, 6}}, {{6, 7}}, {{5, 8}}}, {1, 2, 3, 4, 5, 6, 7, 8}].