TopCoder SRM 480 Div 1 Medium (NetworkSecurity)

Problem Link : http://www.topcoder.com/stat?c=problem_statement&pm=10736

This is a nice graph theory problem. The key observation here is that there is no point placing a data gate on an edge that is not directly connected to a server. Because in this way it can serve maximum number of clients. You might think if a client is connected to all the servers through some path and all the paths share an edge (a bridge) that is not directly connected to a server, why not just place a data gate on that edge as it will be useful for all of the paths? The answer is though it comes handy for the client in question, it does not do any help for the clients that are directly connected to the server. They still need a data gate between them and server. So, we have to place data gates further down the path anyway and that gate on the bridge edge will just be redundant.