← 返回题目列表

Codeforces · 1267/F

F. 傻瓜安全

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Foolprüf Security - 原题 PDF 第 1 页
原题PDF第7页
可复制的 PDF 提取文本
ICPC 2019–2020, NERC – Northern Eurasia Finals
                         St. Petersburg, Barnaul, Tbilisi, and Almaty, December 1, 2019
Problem F. Foolpr¨uf Security

    Time limit:     3 seconds

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 Pr¨ufer 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 Pr¨ufer 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 Pr¨ufer 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 Pr¨ufer code of the map.

Input

The first line of the input contains four integers n, m, ka, and kb (2 ≤n, m ≤105; 1 ≤ka, kb;
ka + kb ≤n + m −2). The second line contains ka integers a1, a2, . . . , aka (1 ≤ai ≤n) — Alice’s
part of the map. The third line contains kb integers b1, b2, . . . , bkb (n + 1 ≤bi ≤n + m) — Bob’s part of
the map.

Output

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.

Examples

   standard input     standard output                   Illustration
 4 5 4 2             Yes
 1 3 3 4             1 5                             1         2         3         4
 7 8                 1 6
                     2 7
                     6 3
                                                   5         6         7         8         9                     3 7
                     9 4
                     3 8
                     4 8

 4 3 3 1             No
 3 2 2
 6

Note

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


                                         Page 7 of 15