Consider a peculiar city with $N$ towns and $M$ bidirectional roads $($connecting towns$)$

classified into three types. This city is peculiar due to unconventional regulations

regarding road usage: men are permitted to travel only on roads of types $1$ and $3,$ while

women are permitted to travel only on roads of types $2$ and $3$ exclusively. The Mayor

of the city intends to renovate the city by reconstructing some roads, with the condition

that the normal routine of the citizens should not be hampered.

Now, you are hired as a computer scientist to answer an important question: What is

the maximum number of roads that can be renovated $($remain closed for traffic during

renovation$)$ while ensuring that the city remains connected for both men and women?

The city is said to be connected if it is still possible to travel form any town $x$ to any

town $Y$ using the existing roads.

For the above problem description:

i$)$ Formulate the problem as a graph problem,

ii$)$ Can it be solved using max flow$-$mincut algorithm? If not, then develop the solution using a well$-$known graph algorithm.

iii$)$ Write the pseudo$-$code of the solution.