考虑每次操作能对答案产生的影响
记每次操作为\(swap(a,b)\),dp[i]表示答案,初始化位-1表示状态不可达,开始时dp[k] = 0.
- a不可达
- b可达 dp[v] = dp[u], dp[u] := dp[u] + 1.
- b不可达 无影响.
- a可达
- b可达 dp[v] = min(dp[v] + 1, dp[u]) dp[u] = min(dp[u] + 1,dp[v]).
- b不可达 dp[u] = dp[v], dp[v] := dp[v] + 1.
const int maxn = 1e6 + 7;
int n, t, m, k;
int dp[maxn];
void solve() {
cin >> t;
while (t--) {
cin >> n >> m >> k;
memset(dp, -1, sizeof dp);
dp[k] = 0;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
int su = dp[u], sv = dp[v];
if (su == -1 && sv == -1) continue;
if (su == -1) dp[v] = sv + 1, dp[u] = sv;
if (sv == -1) dp[u] = su + 1, dp[v] = su;
if (su != -1 && sv != -1) dp[u] = min(sv, su + 1), dp[v] = min(su, sv + 1);
}
for (int i = 1; i <= n; i++)
i == n ? cout << dp[i] << "\n" : cout << dp[i] << " ";
}
}