Cool problem! We'll show a somewhat stronger statement. We can translate the problem into graph theory as follows. Let $v_1, v_2, \cdots, v_n$ be the vertices of a graph. To each ordered pair $(v_i, v_j)$ of the vertices for $i \neq j$ assign it to one of the $n-1$ colors $1, 2, \cdots, n-1$ so that the following condition is satisfied. For each $1 \le i \le n$, the ordered pairs $(v_i, v_j)$ for $j \neq i$ are all assigned different colors. We will show that we can locate $n-1$ ordered pairs $(v_i, v_{b_i})$ for $1 \le i \le n-1$ so that the undirected edges $v_i v_{b_i}$ collectively form a tree and all the ordered pairs are assigned to different colors. It's not hard to see that this would solve the problem at hand. So let's do this algorithmically. Start by selecting the ordered pairs $(v_1, v_n), (v_2, v_n), \cdots, (v_{n-1}, v_n).$ For each color $1 \le c \le n-1$ which is present among the colors assigned to $(v_i, v_n)$ for $1 \le i \le n-1$, select an arbitrary vertex $v_j$ so that $(v_j, v_n)$ is assigned to color $c.$ Designate $v_j$ as an anchor , we will not be touching the ordered pair $(v_j, v_n)$ throughout the following process. Initially, call the colors $c_i$ which are present among the colors assigned to $(v_i, v_n)$ for $1 \le i \le n-1$ tasty. Repeat the following operation until all vertices except $v_n$ are anchors and all colors are tasty. Throughout our process, we will maintain the properties that the number of anchors and tasty colors are equal, and that all colors which appear among the $(v_i, v_{b_i})$ are precisely the tasty colors. Select an arbitrary $v_i$ which is not an anchor. Let $v_{x_1}, v_{x_2}, \cdots, v_{x_k}$ denote the anchors at this point. The tasty colors at this point are precisely the colors assigned to $(v_a, v_{b_a})$ where $a \in \{x_1, x_2, \cdots, x_k\}.$ In particular, there are $k$ tasty colors at this point. Note that there are $k+1$ colors assigned to the ordered pairs $(v_i, v_n), (v_i, v_{x_1}), \cdots, (v_i, v_{x_k})$, and so we can select a $t \in \{x_1, x_2, \cdots, x_k\}$ so that $(v_i, v_t)$ is not tasty ($(v_i, v_n)$ was tasty originally). Replace $b_i$ with $t,$ and let $(v_i, v_t)$ be tasty after this change. Also, let $v_i$ now be an anchor. This operation has the effect of increasing the number of anchors and tasty numbers by one, and so it must terminate because there can be at most $n-1$ anchors. Once it terminates, we claim that we have reached the found the $n-1$ desired ordered pairs. We need only show that the unordered edges $v_i v_{b_i}$ don't form any cycles in the end. Indeed, we'll show that they never form a cycle at any point in the operation. It can be checked that $v_{b_i}$ is always either $v_n$ or an anchor. With this observation, when we apply the operation above on $v_i$, because $v_i$ was selected to not be an anchor, the changing of $b_i$ to $t$ cannot induce cycles because $(v_a, v_i)$ is not one of our ordered pairs for any $a$. So this algorithm indeed generates the desired set of $n-1$ ordered pairs, and so the problem is solved. $\square$

Can you just induct for this one? Take the same graph interpretation as the above post. We'll induct on the number of vertices to prove a stronger claim. Claim: For any directed clique $K_n$ with its $n^2 - n$ directed edges colored with $m\ (\ge n)$ colors such that for every vertex $v_i$, $v_i$ receives $n-1$ distinct colors, then we may label the vertices $v_1,...,v_n$ such that there exists a derangement $(b_i)$ of $n$ with directed edges $v_iv_{b_i}$ forming an undirected tree having $n-1$ colors. Proof: Induct on $n$. In the $K_{n-1}$ not containing $v_n$ each vertex has $n-2$ distinct colors, so by Induction Hypothesis there exists a tree having $n-2$ colors that is a subgraph of $K_{n-1}$. There are $n-1$ colors out of $v_n$, so there must be a color $j$ that is not in the $n-2$-color tree found in $K_{n-1}$, say this edge is $v_nv_{b_n}$. Adding $v_n$ to the tree finishes...?

Solved with mueller.25 Throw all the geometry out and rephrase (after weakening) the problem with graph theory. Given a complete graph on $n$ vertices, every edge is assigned $2$ colors (possibly the same), such that for every vertex, it is possible to choose a color from each edge connected to it such that all $n-1$ edges are colored with distinct colors. We wish to choose $n-1$ edges of distinct colors, which form a tree. But this is just easy, consider the largest possible such tree. Say it has $k$ vertices. Now if there is a vertex outside it, it must be connected to the $k$ vertices in the tree with $k$ distinct colors. But since only $k-1$ colors were used so far, we may add this vertex to the tree, contradicting maximality. Therefore, we can find a tree satisfying the conditions, as desired. $\blacksquare$