Before revision:  We give two algorithms, a deterministic algorithm with  work complexity O( m^2n^2) and a randomized algorithm with  work complexity O( m^2n^2).
After revision:  We give two algorithms, a deterministic algorithm with work complexity O( m^2n^2) and a randomized algorithm with time complexity (mn)^{1/2 + o(1) work complexity O( m^2n^2).