Задача: Найти эйлеров цикл в неориентированном графе. $$$N <= 10^5$$$ $$$M <= 3*10^5$$$

На вики-конспектах сказано: «Если реализовать поиск ребер инцидентных вершине и удаление ребер за O(1), то алгоритм будет работать за O(E). Чтобы реализовать поиск за O(1), для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство deleted бинарного типа» Но если взять граф на двух вершинах c $$$10^5$$$ рёбер между ними, то получаем сложность $$$O(M^2)$$$. Я неправильно понял идею или действительно так получается? Если так получается, то есть ли другой линейный алгоритм? Или только за $$$mlogm$$$?