dynamic programming problem

In a distant country, a wide river crosses the country east to west. There are n cities vi . , vn on the north bank of the river, and m cities u... U on its south bank. We are also given a set E of pairs (v,, uj) of cities that we would like to be connected with bridges. But since the country is not very advanced technologically, the bridges that we build cannot cross each other (though we do allow several bridges to connect one city to several other cities). We clarify what it nleans for a pair of bridges to cross Bridge viuj, crosses bridge uiuj If]J and i, J. Our goal is to connect as many pairs of cities from E as possible (a pair (vi, uj) of cities is considered connected iff there is a bridge between them) Design an efficient (O(mn) time) algorithm to solve this problem, prove its correctness and analyze its running time. You can receive partial credit for a polynomial time solution. In a distant country, a wide river crosses the country east to west. There are n cities vi . , vn on the north bank of the river, and m cities u... U on its south bank. We are also given a set E of pairs (v,, uj) of cities that we would like to be connected with bridges. But since the country is not very advanced technologically, the bridges that we build cannot cross each other (though we do allow several bridges to connect one city to several other cities). We clarify what it nleans for a pair of bridges to cross Bridge viuj, crosses bridge uiuj If]J and i, J. Our goal is to connect as many pairs of cities from E as possible (a pair (vi, uj) of cities is considered connected iff there is a bridge between them) Design an efficient (O(mn) time) algorithm to solve this problem, prove its correctness and analyze its running time. You can receive partial credit for a polynomial time solution