There are several cities in a country, and some pairs of those cities are connected by one-way roads (although it is possible that there are one-way roads both from A to B and from B to A). It is possible to get from any city to any other city using roads. A traveler starts from some city, and travels along one of the roads every day. A number *x* is called *vacation-friendly* if a traveler can have an *x*-day long vacation. That means he can start from some city, travel exactly *x* roads, and be back at the city where he started.
A *vacation string* is an infinite string of '0' and '1' digits, which has a '1' in the *x*-th (1-based) position if and only if *x* is a vacation-friendly number.
For example, consider the country shown in the following picture.
Its vacation string is "0011011111111...": 0->1->3->0 is a 3-day vacation, 0->1->2->3->0 is a 4-day vacation, 0->1->3->0->1->3->0 is a 6-day vacation, 0->1->2->3->0->1->3->0 is a 7-day vacation, and so on.
It turns out that every vacation string becomes periodic at some point. We will enclose the period in parentheses to obtain a finite representation for a vacation string. For example, the above vacation string can be represented by "00110(1)" or "00110111(11)". We will call the shortest possible representation *canonical*.
Given a description of a country as a String[] **arcs**, where the *j*-th character of the *i*-th element of **arcs** is 'Y' if there is a road from city *i* to city *j*, and 'N' otherwise, return the canonical representation of its vacation string. |