There are n cities in the Kingdom. Some pairs of cities are connected by bidirectional roads, and there exists a path between every pair of cities.
The King thinks that supporting so many roads is very expensive, so he decided to close some of them.
He wants to close as many roads as possible, but, of course, he still wants each city to be reachable from any other city.
A city is a dead end if it is connected to only one other city by a direct road. You will be given a String roads, with the j-th character of the i-th element of roads being '1' (one) if the i-th and j-th cities are connected by a direct road, and '0' (zero) otherwise. Return the maximal number of dead ends the Kingdom may have after the reform.