You may know the mathematician von Koch by his famous snowflake. However he has more interesting computer science problems up his sleeves. Indeed, let's take a look at this conjecture:
Given a tree with
n nodes (thus
n-1 edges). Find a way to enumerate the nodes from
n and, accordingly, the edges from
n-1 in such a way, that for each edge
k the difference of its node numbers equals to
k. The conjecture is that this is always possible.
Here's an example to make it perfectly clear :
Your code will take as input a tree, you can take the format you want but for the test cases I will provide the tree by their arcs and the list of their nodes.
For example this is the input for the tree in the picture :
[a,b,c,d,e,f,g] d -> a a -> b a -> g b -> c b -> e e -> f
Your code must return the tree with nodes and edges numbered. You can return a more graphical output but I will provide this kind of output for the test cases :
[a7,b3,c6,d1,e5,f4,g2] d -> a 6 a -> b 4 a -> g 5 b -> c 3 b -> e 2 e -> f 1
[a,b,c,d,e,f,g] [a7,b3,c6,d1,e5,f4,g2] d -> a d -> a 6 a -> b a -> b 4 a -> g => a -> g 5 b -> c b -> c 3 b -> e b -> e 2 e -> f e -> f 1 [a,b,c,d] [a4,b1,c3,d2] a -> b a -> b 3 b -> c => b -> c 2 b -> d b -> d 1 [a,b,c,d,e] [a2,b3,c1,d4,e5] a -> b a -> b 1 b -> c b -> c 2 c -> d => c -> d 3 c -> e c -> e 4
This is code-golf this the shortest answer in bytes win!
Note : This is stronger than the Ringel-Kotzig conjecture, which states every tree has a graceful labeling. Since in the Koch conjecture it is not possible to skip integers for the labeling contrary to the graceful labeling in the Ringel-Kotzig conjecture. Graceful labeling has been asked before here.