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.

My rating is 1901, when I try to register the page says that my rating has to be less than or equal to 1899. However there is no div1 round at the same time. Is this round only for strict div2 users?