I was solving some problems from contests but can't figure out how to solve this problem in the given time constraints.

My attempts: 1. I was making the brute force solution O(n^2). 2. I thought for Graphs and Connected components size but I m not able to do under given constraints.