2019 ACM NEERC, Semifinal

Foolpruf Security

Alice and Bob obtained a map of the secret underground facility. The facility consists of n security units and m chemical labs, connected by bidirectional tunnels. The map of this facility forms a tree: there are exactly n + m - 1 tunnels, and there are no cycles. Vertices corresponding to security units have numbers from 1 to n, chemical labs have numbers from n + 1 to n + m. Each tunnel connects a security unit to a chemical lab; there are no tunnels between two security units or two chemical labs.

In case Alice or Bob gets captured, they decided to split the map into two pieces. To do that, they calculated the Prufer code of the tree. Alice then saved some of the numbers between 1 and n to her data storage in the same order as they go in the original code, and Bob saved some of the numbers from n + 1 to n + m to his storage in the same way.

A Prufer code of a tree on k vertices is a sequence of k - 2 integers from 1 to k, constructed as follows. Find the leaf (a vertex with degree one) with the smallest label, remove it from the tree, then print the label of its only neighbor. Repeat this k - 3 more times, until only one edge remains. The printed sequence of k - 2 vertex labels is the Prufer code.

Alice and Bob safely returned and they are ready to combine their data to restore the original map. They could make a mistake during the backup, meaning no such map exists. Alice and Bob need your help to restore any possible map of the facility consistent with the collected data, so that both Alice’s and Bob’s parts are subsequences of the Prufer code of the map.


The first line contains four integers n, m, ka and kb (2n, m105, 1ka, kb, ka + kbn + m - 2). The second line contains ka integers a1, a2, ..., aka (1 ≤ ain) - Alice’s part of the map. The third line contains kb integers b1, b2, ..., bkb (n + 1bin + m) - Bob’s part of the map.


If there’s no such map, print "No".

Otherwise, print "Yes" on the first line, followed by n + m - 1 lines describing the possible facility map.

Each line should contain two integers ui and vi - the security unit and the chemical lab connected by the i-th tunnel of the facility.


The Prufer code of the tree in the first example is (7, 1, 6, 3, 3, 8, 4).


Time limit 1 second
Memory limit 128 MiB
Input example #1
4 5 4 2
1 3 3 4
7 8
Output example #1
1 8
2 7
3 7
4 9
5 1
6 3
7 4
8 3
Input example #2
4 3 3 1
3 2 2
Output example #2
Source 2019 ACM NEERC, Semifinals, December 1, Problem F