Largest Prime Subgraph

You are given a network of N cities connected by M bidirectional roads. The cities are numbered from 1 to N. Your task is to compute the size of the connected component that contains city 1, and then determine the largest prime number that is less than or equal to this component's size. If no prime number exists in the range [2, component size], output -1.

In mathematical terms, let \( C \) be the size of the connected component containing city 1. You need to find the maximum prime \( p \) such that \( p \leq C \). The function is_prime(n) checks for primality, and you are expected to use a Breadth-First Search (BFS) starting from city 1 to compute \( C \).

Below is an example:

Example:
Input:
5 4
1 2
1 3
3 4
4 5

Explanation:
The component containing city 1 has 5 cities. Since 5 is a prime number, the answer is 5.

inputFormat

The first line contains two integers N and M --- the number of cities and the number of roads, respectively. Each of the following M lines contains two integers u and v indicating that there is a bidirectional road connecting city u and city v.

You should read the input from standard input (stdin).

outputFormat

Output a single integer representing the largest prime number \( p \) such that \( p \leq C \), where \( C \) is the number of cities in the connected component that contains city 1. If no such prime exists, output -1. The output should be printed to standard output (stdout).

5 4
1 2
1 3
3 4
4 5

5