CF589H Tourist Guide

创建一份旅游指南并不像人们想象的那么容易。一份好的旅游指南应当能恰当地分配游客在全国的流动，并最大化旅游收入。因此，只有在满足若干条件的情况下，指南才能被宣布为官方旅游指南并获得旅游部的批准。 旅游部从全国 $n$ 个城市中选出了 $k$ 个著名城市。基本要求是，为了符合严格的规定并获得旅游部的审批，旅游指南应以著名城市之间的若干条路线组成，且需满足以下条件： - 每条路线的起始城市和终止城市必须是不同的著名城市； - 每个著名城市充当路线端点的次数最多为一次； - 任意两条路线没有公共公路。 请注意，路线可以经过其他著名城市。旅游收入在很大程度上取决于旅游指南中包含的路线数，因此任务是尽可能多地找出符合上述规定的著名城市间路线集合。

第一行包含三个整数 $n, m, k$，分别表示全国城市数、道路数和著名城市数，满足 $1 \leq n \leq 50000, 0 \leq m \leq 50000, 1 \leq k \leq n$。 接下来 $m$ 行，每行两个整数 $a_i, b_i$，表示城市 $a_i$ 和 $b_i$ 之间有一条双向公路。保证 $a_i \neq b_i$，且任意一对城市之间至多只有一条公路。 最后一行为 $k$ 个不重复的整数，表示所有著名城市的编号。所有城市编号为 $1$ 到 $n$。

输出的第一行应包含一个整数 $c$，表示旅游指南中包含的路线数。接下来的 $c$ 行，每行输出一条旅游路线。每条路线格式为：“$t\ v_1\ v_2\ ...\ v_{t+1}$”，其中 $t$ 为路线中经过的公路数，$v_1, v_2, ..., v_{t+1}$ 依次表示沿途经过的城市编号，首尾城市均为著名城市。 如果有多种答案，输出任意一种即可。

由 ChatGPT 5 翻译