Street Detour

The city hall of a large city in Nlogônia has started a program to repave its streets. In Nlogônia, every street directly connects two crossings, and it is either one-way or two-way. By an old royal decree, there is always at least one path from any point of the city to any other point.

The program repairs one street at a time, and the street under repair is closed to traffic. The closure can violate the royal decree and cause chaos in local traffic, since some citizens may be unable to get home from work or to work from home. The city hall can convert some one-way streets into two-way streets, but it prefers to avoid that because two-way streets tend to cause more serious accidents. The city hall prefers to create detours only by reversing the direction of existing one-way streets.

The King of Nlogônia asked you to write a program that, given the description of the streets of a city, determines whether a path between every two points of the city still exists after a given street is closed for repair, even if the directions of other streets have to change.

The input contains several test cases and ends at end of file.

The first line of a test case contains two integers $N$ ($1 \le N \le 10^3$) and $M$ ($1 \le M \le 10^5$), the number of crossings and the number of streets. Crossings are numbered from $1$ to $N$ and streets from $1$ to $M$.

Each of the next $M$ lines describes a street with three integers $A$, $B$ ($1 \le A, B \le N$) and $T$ ($1 \le T \le 2$). $A$ and $B$ are the crossings the street directly connects, and $T$ is its direction: if $T = 1$ the street is one-way from $A$ to $B$; if $T = 2$ the street is two-way.

The given street network satisfies the decree: every crossing can reach every other crossing. The first street listed (street 1) is the one closed for repair.

For each test case, print one line with a single character that tells what the city hall must do to respect the royal decree after the street is closed:

• -: no change to the other streets is needed.
• *: the decree cannot be respected, whatever changes are made to the other streets.
• 1: the decree can be respected only by reversing the directions of some one-way streets.
• 2: the decree can be respected, but some one-way streets must be converted into two-way streets.

The four cases are checked in this order: print the character of the first case from the top that applies.