Look at Problem J5S3, Strategic Bombing, from 2001. This will help provide insight into the problem.
http://cemc.uwaterloo.ca/ccc/past/docs/2001_Computing_Contest_(E).pdf

You might notice, the two questions are almost identical!

Here are some distinctions:

    2001 - You want to find the roads that disconnect A from B
    2007 - You want to find the roads that disconnect A from any other point

    2001 - When you find a disconnecting road, you output it
    2007 - When you find a disconnecting road, you add a "bandaid" road from the current node to node A, so that the surrounding disconnecting roads are remedied for the mean time.

    2001 - You are reporting the number of disconnecting roads
    2007 - You are reporting the number of roads which will remedy the disconnected roads (Hint: this is not the number of "bandaid" roads! Look at it visually)


Now let's look at why both problems are in fact, the same question:

Both the 2001 and 2007 version are essentially asking you to find the number of strongly connected components. 
Strongly connected components are nodes grouped together, according to which roads are the only existant path to that node. Nodes that share the same critical road, belong to the same strongly connected component.


What does that mean? 

In 2001, the number of disconnecting roads it the number of strongly connected components between A and B.
In 2007, the number of roads that need to be remedied is the number of strongly connected components in the entire graph.


So... in a way... you might realize that the 2007 version is actually an easier version of 2001's problem, because there aren't as many restrictions.
That statement, in my opinion, is true!

However, if you solved the 2001 version via brute force (blowing up roads at random, and then testing for transitive closure), 
then your algorithm may be too slow on 1000 verticies, and may need to rethink a smarter way to find strongly connected components. 
Also, adjusting the algorithm to meet the three primary distinctions between the questions, may be a hassle. 

I have not actually tested translating the brute force algorithm from 2001, because I haven't wrote one for either year...

Hopefully this will be enough information to get you thinking and solve the problem. 
The problem becomes easy once you figure out a way to efficiently find disconnecting roads.

You can also see my solution to the 2001 version by clicking on the alternate solution, "Strategic Bombing 2001", back on the main page. But that will give away my algorithm to finding strongly connected components.