看到 shortest paths 来做的，但是好像没啥关系也没啥难度。
首先能知道一个连通块肯定一次就能跳完，所以可以把连通块缩出来。
然后有一个性质，记 \(cz_i\) 为 \(i\) 连通块内点种通过已知边推出的度数为 \(1\) 的个数为 \(cz_i\)，则 \(cz_i\bmod 2 = 0\)。
记点 \(i\) 通过已知边推出的度数为 \(d_i\)，大致证一下，分三种情况：
- \(d_u = 0, d_v = 0\)，个数 \(+2\)。
- \(d_u = 1, d_v = 1\)，个数 \(-2\)。
- \(d_u = 0, d_v = 1\)，个数不变。
对于 \(cz_i\) 对答案的贡献，分两种情况考虑：
- \(cz_i = 0\)，则这部分肯定会产生 \(1\) 的贡献。
- \(cz_i > 0\)，则很显然可以通过让两个度数为 \(1\) 的点相连是 \(cz_i\) 变为 \(\le cz_i\) 的任何偶数。
则当 \(cz_i = 0\) 时，每个连通块都会产生 \(1\) 的贡献，即最大值；
当 \(cz_i = 2\) 时，可以对于每一个 \(cz_i = 2\) 的连通块相连成一个环，所有连通块只会产生 \(1\) 的贡献，即最小值。
// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int fa[N], dz[N];
int hv[N], cz[N];
int main() {
int Tcs;
scanf("%d", &Tcs);
function<void ()> solve = []() -> void {
// printf("\n");
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
fa[i] = i, dz[i] = 0;
}
function<int (int)> getfa = [&getfa](int u) -> int {
return fa[u] == u ? u : (fa[u] = getfa(fa[u]));
};
map<pair<int, int>, bool> l;
function<void (int, int)> add = [getfa, &l](int u, int v) -> void {
if (! l[{u, v}]) {
l[{u, v}] = l[{v, u}] = 1, dz[u]++, dz[v]++;
}
u = getfa(u), v = getfa(v);
if (u == v) {
return ;
}
fa[u] = v;
return ;
};
for (int i = 1; i <= n; i++) {
int v;
scanf("%d", &v);
add(i, v);
}
for (int i = 1; i <= n; i++) {
hv[i] = cz[i] = 0;
}
for (int i = 1; i <= n; i++) {
// printf("%d ", dz[i]);
int f = getfa(i);
hv[f] = 1, cz[f] += (dz[i] == 1);
}
// printf("\n");
int ul = 0, ufl = 0;
for (int i = 1; i <= n; i++) {
if (hv[i]) {
// printf("%d ", cz[i]);
ul += (cz[i] > 0), ufl += (cz[i] == 0);
}
}
// printf("\n");
// printf("ul = %d, ufl = %d, ans = ", ul, ufl);
printf("%d %d\n", (ul > 0) + ufl, ul + ufl);
return ;
};
for (; Tcs; Tcs--) {
solve();
}
return 0;
}