Hasinur's Mission!

This is a simple DP problem with a little of combinatorics in it. If you have the basic idea of dynamic programming, you might have solved this problem already in the contest.

So, we have to calculate from a certain node how many other nodes are there along the way where he will pass at least one road with prime numbers. Then if there is a total of x nodes from the node y where he will meet the condition. The answer will be increased to (xP2 = x permutation 2) or simply x × (x-1). You can calculate the number of nodes y from every node x by a single or two DFS using dynamic programming.

Expected run-time complexity: O(n).