$\textbf{This is an approximate problem.}$

Consider a complete undirected graph with $N$ vertices. You select a spanning tree from the graph, after that every edge $(i,j)$ in the tree will be deleted with probability $p_{i,j}$ and with probability $1 - p_{i,j}$ remains. In the remaining  forest for every $i$ you compute $D(i)$, the biggest distance from $i$ to other accessible vertex $j$. You want to maximize the expected value of $S = \sum_{k = 1}^{N} D(k)$.

$\textbf{Input}$

The first line contains two integers - $N, T (N = 42)$ where $T$ is the type of the test.

The $(i + 1)^{th}$ line contains $N$ nonegative integers - $q_{i,1}, q_{i,2}, \dots, q_{i,N} (0 \le q_{i,j} = q_{j,i} \le 10^6, q_{i,i} = 0)$, $p_{i,j} = \frac{q_{i,j}}{10^6}$

$\textbf{Output}$

Output $N - 1$ lines, each line will contain two numbers - $u,v$, meaning that there is edge $(u,v)$ in the chosed tree.

$\textbf{Tests}$

The will be $60$ tests generated by the following algorithms:

$T = 1$, $q_{i,j}$ is generated uniformly in interval $[0,10^6]$.

$T = 2$, $q_{i,j}$ is generated uniformly in interval $[0,2 \cdot 10^5]$.

$T = 3$, $q_{i,j}$ is generated uniformly in interval $[0,10^6]$. After this it is applied Roy-Floyd shortest path algorithm on matrix $q$, thus obtaining $q_{i,j} \le q_{i,k} + q_{k,j}$.

After the contest the current tests will be replaced by others generated with a different seed.

$\textbf{Score}$

The score will be $e^{\frac{S}{\alpha(T)}}$ where $\alpha(1) = 80$ , $\alpha(2) = \alpha(3) = 100$ and $e \approx 2.718281828459$.