Before revision:  Furthermore, for any integer k \geq 1 we give an algorithmfor maintaining\tilde{O}, and |E|= n^{1+\Omega(1)}.
After revision:  Furthermore, for any integer k \geq 1 we give an algorithmfor maintaining\tilde{O}(s) amortized update time, assuming that s= n^{\Omega(1), and |E|= n^{1+\Omega(1)}.