问题描述

现有一棵树, 树上有 \(n\) 个编号从 \(1\) 到 \(n\) 节点及 \(2n - 2\) 条有向边.
保证当有向边 \(u \rightarrow v\) 存在时, 有向边 \(v \rightarrow u\) 也存在.
树上任意两个节点都可以互相到达.

树上任意两个节点之间都可以互相传递消息.
定义 \(u \Rightarrow v\) 为 \(u\) 作起点, \(v\) 作终点的有向简单路径, 当节点 \(u\) 向节点 \(v\) 传递消息时, 这条消息将会经过路径 \(u \Rightarrow v\) 上的节点和有向边各一次.

树上每个点有一个权值, 初始为 \(0\). 当一条消息在传递的过程中经过有向边 \(u \rightarrow v\) 时, 如果 \(u < v\), 则节点 \(u,v\) 的权值各 \(+1\), 反之则各 \(-1\).

在经过若干次消息传递后, 树上节点的权值已经发生了变化. 现在给定所有点最终的权值, 要求你给出字典序最小的传递消息的方案, 使得最终的权值与输入吻合. 具体要求见输出格式.

输入格式

第一行一个整数 \(n\).

第二行 \(n\) 个整数, 依次表示节点 \(1...n\) 的最终权值.

接下来 \(n-1\) 行, 每行两个整数 \(u_i, v_i\), 表示存在两条有向树边 \(u_i \rightarrow v_i\) 和 \(v_i \rightarrow u_i\).

输出格式

第一行一个数 \(m\).

接下 \(m\) 行, 每行两个数, 其中第 \(i\) 行为两个整数 \(u_i, v_i\), 表示一次消息由 \(u_i\) 传向 \(v_i\).

本题要求 字典序最小 , 具体地:

_满足 \(m\) 最小的前提下依次保证 \(u_1, v_1, u_2, v_2, ..., u_m, v_m\) 尽可能小._

数据范围

对于 \(100\%\) 的数据, \(0 < n \leq 10^6\), 保证存在 \(m\) 使得 \(m \leq n\).