Mr. Kitayuta’s Colorful Graph (A graph with $m$ edges can have at most $\mathcal{O}(\sqrt{m})$ nodes of degree greater than $\sqrt{m}$ $\implies$ there are at most $\mathcal{O}(\sqrt{m}\times\sqrt{m}) = \mathcal{O}(m)$ pairs of nodes $(u,v)$ such that both have degree greater than $\sqrt{m}$.)
Chef and Churu ($\mathcal{O}(q\sqrt{n})$. Needs two sqrt decomposition.)