Будем использовать DSU "с откатами" т.е. такой DSU который умеет вернуться к предыдущему состоянию. возьмём K порядка sqrt(E). Разобъём рёбра на блоки длины K. Все запросы оба конца которых лежат в одном блоке решим влоб с помощью DSU — O(K) на запрос. Остальные запросы обработаем так:

for (int i = 0; i < E / K; ++i)
{
    int cL = i * K;
    int cR = cL + K;
    DSU dsu;
    for (int R = cR; R < N; ++R) 
    {
        dsu.addEdge(edge[R]);
        для всех запросов q таких что cL <= q.L < cR && q.R == R
        {
            //все рёбра таких запросов уже добавлены в DSU, за исключением не более K
            запомнить состояние dsu
            for (int j = q.L; j < cR; ++j)
                dsu.addEdge(edge[j]);
            q.Answer = dsu.GetAnswer();   
            восстановить состояние dsu  
        }
    }
}