Hi. During an algorithm training to prepare the French IOI candidates, we came across a problem, and were wondering about the best complexity to solve it. Here is the statement:

You are given a directed graph with N nodes, that is initially empty. There are M queries that have to be answered online (this is important otherwise the problem is trivial). In each query, an edge is added in the graph, and you have to print whether or not after the edge is added there is a cycle in the graph or not. (Once the first cycle is found, obviously the answer will be yes for all queries after.)

I was hoping that the codeforces community could help us find new and faster solutions to this problem.