There is a country with \(N\) villages and each village has a number associated with them and \(M\) roads, a road connects two different villages
In this country, the Prime minister decided to test the hospitals to see if they can handle another wave of the coronavirus pandemic.
A village has the vaccine if the number associated with it is a prime number (villages numbered 2,3,5,7,11... will have a vaccine with them)
For each village find the minimum time required for the vaccine to arrive there if for each road between villages \(u\) and \(v\) it takes \(max(u,v)\) time to travel this road

Note: The graph does not have self-loops or multi edges

Input :
The first line will contain \(N\) and \(M\), the number of villages and the number of roads respectively
The next \(M\) lines contain two integers \(u\) and \(v\) (meaning there is a road between villages \(u\) and \(v\) and it takes \(max(u,v)\) time to travel this road)\(\)

Output:
Print \(N\) space-separated integers which is the minimum time for the vaccine to arrive at that village, if it's impossible for the vaccine to arrive at a particular village then print -1

Constraints:

\(1 \leq N \leq 2*10^5\)

\(0 \leq M \leq min(2*10^5,(N*(N-1))/2)\)

\(1 \leq u,v \leq N\)