Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly.

Given an undirected tree with N nodes rooted at 1. Every node is assigned a weight which is given by an array A. Weight of an edge W(u, v) is defined as (A[u] + A[v]) * (A[u] | A[v]), where | represents Bitwise OR operator.

You are allowed to perform at most K operations on tree and in each operation:

Choose u v, and reverse the weights of the nodes present on the simple path between node u and v.

Suppose, X such operations are performed, maximize the value of Z = (Sum of weight of all the edges of the tree) * (K - X + 1)

Input Format:

First line contains two space separated integers N K.
Second line contains N space separated integers denoting the weight of the nodes.
Next N - 1 lines contains two space separated integers u v, denoting an edge between node u and v.

Output Format:

Print X, denoting the number of operations performed.
In next X lines, print the pair of nodes u v choosen in given operation.

Constraints:

\(N = 10^4 \\ K = 10^2 \\ 1 \le A[i] \le 10^6 \\ 1\leq u, v \leq N\)

Verdit and Scoring

Z is the score for each test case.
If the value of X is greater than K or pair of nodes choosen in operation is invalid, then you will receive a Wrong Answer verdict.