P17893 [ICPC 2026 Nanchang I] One Touch Drawing

题目描述

枫蜜最近迷上了一款名为“一笔画”的小游戏。在这个游戏中,地图是一张包含 $n$ 个节点和 $m$ 条边的无向图,图中可能存在重边和自环,且不一定连通。玩家需要从某个节点出发,沿着图中的边行走,恰好经过每条边一次,最后可以停留在任意节点。当所有边都被经过恰好一次后,游戏立刻结束。 这款游戏增加了一个特殊的“传送”机制:有 $k$ 对互不相同的“跳跃点”,每对 $(a, b)$ 具有如下性质:每当玩家经过一条边到达节点 $a$ 或节点 $b$ 时,会立刻被传送到该点对中的另一个节点,并在传送后继续行动。 需要特别注意的是: - 起点不会触发传送(即如果起点是一个跳跃点,从该点出发时不会发生传送); - 终点也不会触发传送(即如果最后一步到达一个跳跃点,游戏立即结束,不再进行传送)。 枫蜜想要知道,是否存在一条路径,使得玩家从某个节点出发,经过每条边恰好一次,并严格遵守上述跳跃规则。如果存在,请输出任意一条这样的路径(以经过的节点序列表示),或报告无解。

输入格式

第一行包含一个正整数 $t$ ($1 \le t \le 5\times 10^4$),表示测试数据组数。 对于每组数据: 第一行包含三个正整数 $n$、$m$ 和 $k$ ($2 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le k \le \lfloor \frac{n}{2} \rfloor$),分别表示节点的数量、边的数量和跳跃点对的数量。 接下来 $m$ 行,每行包含两个正整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$),描述一条无向边(可能存在重边和自环)。 接下来 $k$ 行,每行包含两个正整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$),表示 $(a_i, b_i)$ 是一对跳跃点。保证所有 $a, b$ 互不相同(即每个节点至多出现在一对跳跃点中)。 保证所有数据的 $n$ 之和不超过 $10^5$,$m$ 之和不超过 $10^6$。

输出格式

对于每组数据,如果存在满足条件的路径: 第一行输出一个整数 $L$,表示路径经过的节点个数(包括起点和终点); 第二行输出 $L$ 个整数,两两之间以一个空格分隔,表示依次经过的节点编号。 如果不存在,输出一行 $-1$。 注意:路径序列中需要记录实际到达的节点(包括传送后到达的节点)。例如,从节点 $1$ 走到 $2$(假设 $2$ 是跳跃点,传送到 $3$),然后从 $3$ 走到 $4$,则输出序列为 $[1,2,3,4]$。

说明/提示

对于样例的第一组数据,$(5,7)$ 是一对跳跃点,如图所示。 一条可行的路径是:$1 \to 2 \to 3 \to 4 \to 5$(传送)$\to 7 \to 6 \to 5$(传送)$\to 7 \to 8 \to 9 \to 10 \to 11$。 :::align{center} ![](https://cdn.luogu.com.cn/upload/image_hosting/c6bjrgfq.png) ::: 对于样例的第二组数据,如图所示: :::align{center} ![](https://cdn.luogu.com.cn/upload/image_hosting/q42ox8wc.png) :::