# Untitled

unknown
plain_text
12 days ago
1.7 kB
0
Indexable
Never
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

// Function to find the Kth prime number
int kthPrime(int K) {
vector<int> primes;

while (primes.size() < K) {
bool isPrime = true;
for (int i = 2; i <= sqrt(num); ++i) {
if (num % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primes.push_back(num);
}
++num;
}
return primes[K - 1];
}

// Function to perform BFS and find the size of the connected component
int bfs(int start, vector<vector<int>>& adj, vector<bool>& visited) {
queue<int> q;
q.push(start);
visited[start] = true;
int size = 0;

while (!q.empty()) {
int node = q.front();
q.pop();
++size;

for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
return size;
}

int main() {
int N, M;
cin >> N >> M;

for (int i = 0; i < M; ++i) {
int U, V;
cin >> U >> V;
}

vector<bool> visited(N + 1, false);
int maxLandmarks = 0;

// Find the maximum connected component
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
maxLandmarks = max(maxLandmarks, bfs(i, adj, visited));
}
}

int ferryTicketPrice = kthPrime(maxLandmarks);

cout << maxLandmarks << " " << ferryTicketPrice << endl;

return 0;
}