Using a bitset solves this problem in \(O(\dfrac{nq}{\omega})\), but you can’t pass it under the memory limit because it has a memory complexity greater than \(O(\dfrac{n^2}{8})\).

Alternatively, there is a simple brute force approach that simply stores the neighbours of each vertex with a time complexity of \(O(qn)\).

Combine these two solutions by storing a bitset for each vertex with \(< m\) neighbours, and using a vector for each vertex to store the neighbours \(\geq m\). Then the time complexity will be \(O(\dfrac{mq}{\omega}+q(n-m))\), and it passes when \(m=8 \times 10^3\).

Submission link.