Comments
+12

D is a simultaneously BFS from every city with police. Mark each connected city with nubmer of a source police city, then go through edges and if a "police number" on the left != one on the right, then the edge can be removed. You even don't need the d parameter.