原案：toam

強連結性を保ったまま辺を削除する問題ではなく、 \(N\) 頂点 \(N-1\) 辺のグラフに辺を追加して強連結にする問題と考えます。

辺を \(X\) の昇順にソートします。

\(\mathrm{dp}[i][r]\) を 「 \(i\) 番目の辺までで、頂点1から到達できる頂点の番号の最大値が \(r\) になる方法」とします。この DP の更新は、辺 \((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}\)

この dp を in-place に行うことを考えると、区間和取得・1点更新・区間乗算ができればよく、遅延セグメント木を用いることで \((N+M\log N)\) でこの問題を解くことができます。

実際には \(r< X_i\) の範囲は \(\mathrm{dp}[M][N]\) を求めることには影響しないので更新を省略することができます。