Well, I approached this problem in this way. I found out the bridges of the graph, and since the graph is given to be a connected one, I calculated the number of failed combinations of placing the soldiers and then calculated the probability.

Here is a link to my code

Can anyone point out where am I going wrong!

Here is the link for the problem