6998：鸽子

题目描述

你的机房共有 $n$ 台电脑，但是第 $k$ 台电脑坏了。

你的老师给你 $m$ 次要求，每次要求你将第 $u_i$ 和 $v_i$ 台电脑交换，这样坏的电脑就可能会被交换到一个新的位置。

但由于你希望进行暗箱操作，你可以拒绝执行其中的若干条要求，使得坏的电脑最终交换到 $j$ 号位置。

由于骗过老师很累，请对于 $j=1...n$ 求出最少可能的不执行要求条数，使得坏的电脑在第 $j$ 个位置。

输入解释

本题有多组测试数据。

第一行一个数 $T$ 表示一共有 $T$ 组数据。对于每一组数据：

第一行三个整数 $n, m, k$ ，表示电脑个数，总操作次数和坏电脑的初始位置。

下面 $m$ 行，每行两个正整数 $u_i$ , $v_i$ ，表示这次操作选择的两个位置。

满足 $1 \le T \le 5$，$1 \le n \le 10^5$，$0 \le m \le 10^5$，$1 \le k \le n$。

输出解释

对每组数据，输出共一行 $n$ 个整数，第 $i$ 个整数表示使坏电脑最终停留在该位置所需的最少暗箱操作次数。

若最终坏电脑不可能停留在该位置，则输出 $−1$。

输入样例

输出样例

2 0 3 1 -1

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2021 年百度之星·程序设计大赛 - 初赛一

源链接： HDU-6998

最后修改于 2021-10-23T19:10:59+00:00 由爬虫自动更新

共提交 5 次

通过率 0.0%

时间上限	内存上限
2000/1000MS(Java/Others)	32768/32768K(Java/Others)