Doubt in Kuroni and Cowsheds from June Lunchtime

Subtask1 : N,Q<=5000.
Many have solved the Subtask1 using DSU, where they have joined l,r as they come along. At the end of the query they check the total number of distinct parents, which is there answer.

I tried doing the same-thing, but used dFS instead of dSU. I kept inserting the edges in a set, and at the end of a query I DFSed the graph and found the number of components. My code gives TLE.
Is my implementation incorrect?
Can this question be solved using DFS, or is it must to use DSU?

1 Like

dfs time complexity is O(V+E).Now in worst case E=VV.
So net time complexity is O(Q