✧ ✦ Spark of Exam Luck ✦ ✧

Consider the graph induced by the vertices in an interval $[L,R]$.

The graph must be connected for every student to receive a spark. If a connected graph contains a cycle, a spark can reach that cycle and keep traveling around it forever. Conversely, in a tree, sparks follow the unique paths from the starting vertex. The last delivery happens no later than time $R-L \le N-1$, so the time condition is satisfied. Thus, we need to count intervals whose induced graphs are trees.

For small inputs, inspect every interval directly. Run BFS to check connectivity and check that the number of internal edges is one less than the number of vertices. This takes $O(N^2(N+M))$ time and $O(N+M)$ space.

For the full constraints, fix the left endpoint $L$ and extend the right endpoint $R$, maintaining connected components with a DSU. Add the new vertex $R$ and its edges to neighbors $u$ with $L \le u < R$. An edge within one component creates a cycle. That cycle remains when increases, so stop processing this . Whenever there is no cycle and exactly one component remains, add to the answer. Do not stop merely because the graph is disconnected: a later vertex may join its components.

For each vertex, store only its smaller-numbered neighbors in decreasing order. Stop iterating as soon as a neighbor is smaller than $L$. For a fixed $L$, at most $N-L$ union operations succeed and at most one fails. Including vertex iteration and DSU initialization, the total complexity is $O(M\log N + N^2\alpha(N))$ time and space.

The answer is at most $N(N+1)/2=50\,005\,000$. DSU sizes are at most $10\,000$ and the edge count is at most $1\,000\,000$, so every calculation fits in a signed -bit integer.

Solution written by GPT6