树上基因重组
题号:NC248200
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小松鼠又开始研究树的基因了,他开发出了一种基因重组算法,能根据一些信息很快地还原一棵树,现在他想考考你!

给定一棵 n 个节点的有根树的 dfs 序以及每个点对应的子树大小,求这棵树。

保证有解哦!

输入描述:

输入共三行。
第一行为节点数 n\ (2\leq n\leq 10^6),第二行为这棵树的 dfs 序,第三行为以  为根的每棵子树大小。

输出描述:

输出共 n-1 行。
每行两个正整数表示 (u,v),要求 并且每行的 u 单调不降,对于相同的 u 所对应的 v 需要满足单调递增。
示例1

输入

复制
4
1 2 4 3
4 2 1 1

输出

复制
1 2
1 3
2 4

说明

树的形态如下图所示:

示例2

输入

复制
3
3 1 2
1 1 3

输出

复制
1 3
2 3

说明