Untitled

#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;
    int num = 2; // Start with the first prime number

    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;

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int U, V;
        cin >> U >> V;
        adj[U].push_back(V);
        adj[V].push_back(U);
    }

    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;
}