Original proposer: toam

Instead of removing edges while keeping it strongly connected, interpret the process as adding edges to \(N\)-vertex, \((N-1)\)-edge graph to make it strongly connected.

Sort the edges in ascending order of \(X\).

Let \(\mathrm{dp}[i][r]\) be the number of ways to choose edges out of the first \(i\) edges, so that the maximum vertex number reachable from vertex \(1\) is \(r\). The recurrence relations of this DP (Dynamic Programming) are as follows, considering what happens when adding edge \((X_i,Y_i)\):

\(\mathrm{dp}[i][r]=\begin{cases} 2\mathrm{dp}[i-1][r] & \text{if } r < X_i \\ \mathrm{dp}[i-1][r] & \text{if } X_i \leq r < Y_i \\ \mathrm{dp}[i-1][Y_i]+\sum_{r'=X_i}^{Y_i}\mathrm{dp}[i-1][r'] & \text{if } r=Y_i\\ 2\mathrm{dp}[i-1][r] & \text{if } r>Y_i \end{cases}\)

In order to compute this DP in-place, it is sufficient to preform segment-sum retrieval, element-wise update, and segment-wise multiplication. Thus, by using a lazy segment tree, the problem can be solved in \((N+M\log N)\) time.

In fact, the range \(r< X_i\) does not affect to \(\mathrm{dp}[M][N]\), so we can omit the update.