Online cycle detecting in a directed graph I'm thinking about this problem for a couple of days and still don't know how to deal with it:

We are given integers $n\le 1000,m\le 300000$ - number of vertices and edges respectively. Then we are given edges one by one. Edges are directed and are given by pair of two integers: $(a,b)$ (both from interval $[1..n]$) which means edge from vertex $a$ to vertex $b$. For each edge instantly we have to decide if adding it will create a cycle in constructed graph. If it will - we print this edge and we don't add it to our graph, else we add this edge and print nothing.

So this graph can be quite dense, but it always has very small number of vertices and we should probably use it. Moreover, I guess time complexity will be amortized in a standard solution. Can anybody help?
For example: $n=4, m=5$ and edges in order of appearance:
$2\rightarrow 4, \ 4\rightarrow 3, \ 3\rightarrow 2, \ 1\rightarrow 2, \ 3 \rightarrow 1$, then the answer is: $3\rightarrow 2, \ 3\rightarrow 1$ because adding those edges will create a cycle.
 A: My first thought would be simply to maintain the transitive closure of the edges seen so far as an $n\times n$ array of bits.
On the other hand, updating this array when a new edge is added could be expensive. Without some clever way to reduce this work (better than looking through the Cartesien product of "predecessors of $a$" with "successors of $b$" when we add an edge $a\to b$), the total work done here can end up being $\Theta(mn^2)$, compared to $O(m^2)$ for simply searching for a path from scratch for each edge added.
A: *

*A connected graph on $n$ vertices has no cycles if and only if it has exactly $n-1$ edges. Adding any edge over $n-1$ creates new cycle. 

*If a graph on $n$ vertices has strictly less than $n-1$ edges, it is necessarily disconnected.

*If you have graph with two disjoint components, then connecting them with an edge does not create a new cycle.


This means basically that adding an edge to the graph adds in a new cycle if and only if both edges lie in the same connected component.
