In one country there are n cities numbered from 1 to n. Some of them are connected by one-way roads.
There are n-1 main roads: for all i from 1 to n-1 there is a road from i to i+1,
and there are also some auxiliary roads.
The king of the country decided to divide it into provinces. He wants to create as many provinces as possible. All provinces must contain the same number of cities. Each city must belong to exactly one province. For each pair of distinct provinces A and B, the following condition must be satisfied. If there is a path from some city in A to some city in B, there must be no paths that go from province B to province A.
You are given a int n and a String roads containing all the auxiliary roads in the country. First, concatenate all the elements of roads. The resulting String is a comma-separated list of integer pairs. Each pair is formatted as "i j" (quotes for clarity), which means there's an auxiliary road from i to j. Return the maximum possible number of provinces that can be created.