Tree

Given $n$ points in the plane with target degrees $d_i$ where $\sum d_i = 2n-2$, draw a straight-line tree without crossings so each point $p_i$ has degree $d_i$. Output any valid edge list.

The first line contains $T$. Each test case has $n$ ($4 \le n \le 1000$) followed by $n$ lines with $x_i$, $y_i$, and $d_i$.

For each test case print $n-1$ edges as two indices per line. Any valid solution is accepted.