Vaccine

4.2

4 votes
Graph Theory, Algorithms, Graphs, Sieve, Breadth-first search
Problem

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:

1N2105

0Mmin(2105,(N(N1))/2)

1u,vN

 

Time Limit: 2
Memory Limit: 512
Source Limit:
Explanation

Village number 2,3 and 5 have their own vaccines so the time required for them is 0
Village number 6 is not connected to any village which has a vaccine, therefore -1
Village number 1,4 will get its vaccine in the shortest time from village 2

Editor Image

?