AdditionalFile5626.zip

#5626. 「POI2026 R2」Kontrwywiad

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – II etap Kontrwywiad

在 Bajtocja 有 $n$ 个城市，编号从 $1$ 到 $n$，以及 $n-1$ 条道路，每条道路直接连接两个城市。从任意一个城市出发，都恰好只有一种不经过重复道路的方式到达另一个城市。

你负责对 Bajtocja 的反间谍部门进行管理。你刚刚收到情报，敌对国家 Bitocja 的间谍已经渗透进了某些城市！已知 Bajtocja 的间谍总是成对活动。当其中一名间谍发现有用信息时，他会尝试前往另一名间谍所在的城市进行分享。对于这 $q$ 对间谍，你确切地知道每对间谍所在的城市编号。

你的任务是确保任何一对间谍都无法会合。为此，你可以对任意一组城市宣布实施封锁（隔离）。人们无法进入、穿过或离开被封锁的城市。

当且仅当存在一个由未被封锁的城市组成的序列 $x_{1}, x_{2}, \ldots, x_{k}$ 时，一对间谍才能会合。其中 $x_{1}$ 是其中一名间谍所在的城市，$x_{k}$ 是另一名间谍所在的城市，且对于每个 $1 \leq i \leq k-1$，城市 $x_{i}$ 和 $x_{i+1}$ 之间都有一条道路直接相连。

当然，你并不希望瘫痪整个国家，因此你希望封锁尽可能少的城市。你的任务是计算为了阻止所有间谍对会合，最少需要封锁多少个城市。此外，你还需要提供满足该要求的任意一组最短城市名单。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(2 \leq n \leq 5 \cdot 10^{5}, 1 \leq q \leq 5 \cdot 10^{5})$，分别表示比特托邦的城市数量和间谍对的数量。

接下来的 $n-1$ 行描述了道路。第 $i$ $(1 \leq i \leq n-1)$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示城市 $a_{i}$ 和 $b_{i}$ 之间由一条道路直接相连。

接下来的 $q$ 行描述了间谍对。第 $i$ $(1 \leq i \leq q)$ 行包含两个整数 $c_{i}$ 和 $d_{i}$ $(1 \leq c_{i}, d_{i} \leq n, c_{i} \neq d_{i})$，表示第 $i$ 对间谍所在的城市（一名间谍在城市 $c_{i}$，另一名在城市 $d_{i}$）。一个城市中可能会有多个间谍（来自不同的间谍对）。

输出格式

第一行输出一个整数 $s$，表示为了阻止所有间谍对会合，最少需要封锁的城市数量。

第二行输出 $s$ 个整数，表示满足该要求的一组封锁城市名单。

样例

输入

7 3
1 2
1 3
2 4
2 5
2 6
3 7
1 5
1 6
3 7

输出

2
2 3

有三对间谍，在图中分别用字母 $A$、$B$ 和 $C$ 标记。如果封锁城市 $2$ 和 $3$（用圆圈标记），那么任何一对间谍在不经过这些城市的情况下都无法会合。其他正确的封锁城市名单还包括例如 $\{1, 3\}$ 和 $\{1, 7\}$。

附加样例

1. $n=10, q=5$。
2. $n=500000, q=250000$，对于 $1 \leq i \leq n-1$ 有 $a_{i}=i, b_{i}=i+1$（链状图）；对于奇数 $1 \leq i \leq q$ 有 $c_{i}=4 \cdot \lfloor\frac{i-1}{2}\rfloor+1, d_{i}=4 \cdot \lfloor\frac{i-1}{2}\rfloor+3$；对于偶数 $1 \leq i \leq q$ 有 $c_{i}=4 \cdot \lfloor\frac{i-1}{2}\rfloor+2, d_{i}=4 \cdot \lfloor\frac{i-1}{2}\rfloor+4$。
3. $n=262143, q=17$，对于 $1 \leq i \leq n-1$ 有 $a_{i}=i+1, b_{i}=\lfloor\frac{i+1}{2}\rfloor$；对于 $1 \leq i \leq q$ 有 $c_{i}=2^{i}-1, d_{i}=2^{18}-2^{18-i}$。
4. $n=500000, q=499999$，对于 $1 \leq i \leq n-1$ 有 $a_{i}=1, b_{i}=i+1$；对于 $1 \leq i \leq q$ 有 $c_{i}=1, d_{i}=i+1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

如果你只输出了正确的第一行（即最小数量 $s$），你的程序将获得该测试点 $80\%$ 的分数。为了获得这部分分数，你不需要输出第二行。