침대 밖은 위험해!

#include<iostream>
#include<vector>
using namespace std;

int t, n;
vector<int> a;
vector<bool> check;

void dfs(int now){
	check[now] = true;

	if (!check[a[now]])
		dfs(a[now]);
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		a = vector<int>(n + 1);
		check = vector<bool>(n + 1, false);
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		int ans = 0;
		for (int i = 1; i <= n; i++)
			if (!check[i]){
				ans++;
				dfs(i);
			}
		cout << ans << "\n";
	}
}

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int t, v, e;
vector<vector<int> > g;
vector<int> check;

bool bfs(){
	queue<int> q;
	for (int i = 1; i <= v; i++){
		if (check[i] == 0){
			q.push(i);
			check[i] = 1;

			while (!q.empty()){
				int now = q.front();
				q.pop();

				for (int j = 0; j < g[now].size(); j++){
					if (check[g[now][j]] == 0){
						q.push(g[now][j]);
						check[g[now][j]] = ~check[now] + 1;
					}
					else if (check[now] + check[g[now][j]] != 0){
						return false;
					}
				}
			}
		}
	}
	return true;
}

int main(void){
	cin >> t;
	while (t--){
		cin >> v >> e;
		g = vector<vector<int> >(v + 1);
		check = vector<int>(v + 1, 0);
		int a, b;
		for (int i = 0; i < e; i++){
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}

		if (bfs()) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;

int t, v, e;
vector<vector<int> > g;
vector<int> check;

bool dfs(int now, int c){
	check[now] = c;

	for (int i = 0; i < g[now].size(); i++)
		if (check[g[now][i]] == 0){
			if (!dfs(g[now][i], -c))
				return false;
		}
		else if (check[now] == check[g[now][i]])
			return false;
	return true;
}

int main(void){
	cin >> t;
	while (t--){
		cin >> v >> e;
		g = vector<vector<int> >(v + 1);
		check = vector<int>(v + 1, 0);
		int a, b;
		for (int i = 0; i < e; i++){
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}

		bool isBi = true;
		for (int i = 1; i <= v; i++)
			if (check[i] == 0)
				if (!dfs(i, 1)) {
					isBi = false;
					break;
				}

		if (isBi) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
	return 0;
}

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int n, m, ans = 0, check[1001];

int main(void){
	cin >> n >> m;
	vector<vector<int> > g(n + 1);
	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	queue<int> q;
	for (int i = 1; i < n + 1; i++){
		if (!check[i]){
			ans++;
			q.push(i);
			check[i] = true;

			while (!q.empty())
			{
				int now = q.front();
				q.pop();

				for (int j = 0; j < g[now].size(); j++){
					if (!check[g[now][j]]){
						q.push(g[now][j]);
						check[g[now][j]] = true;
					}
				}
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;

int n, m, ans, check[1001];
vector<vector<int> > g;

void dfs(int now){
	check[now] = true;

	for (int i = 0; i < g[now].size(); i++){
		if (!check[g[now][i]])
			dfs(g[now][i]);
	}
}

int main(void){
	cin >> n >> m;
	g.resize(n + 1);
	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	for (int i = 1; i < n + 1; i++){
		if (!check[i]){
			ans++;
			dfs(i);
		}
	}
	cout << ans << "\n";
	return 0;
}