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.