Road Roles

Andy has finished wiring a connected undirected network of $n$ cities with $m$ weighted roads. He now wants to know how each road relates to the Minimum Spanning Trees of the network.

For each road, classify it as one of:

• forced — the road appears in every MST;
• optional — the road appears in some MST, but not all;
• useless — the road appears in no MST.

Input

The first line contains integers $n$ and $m$.

The following $m$ lines each contain three integers $a$, $b$, and $c$, describing an undirected road between cities $a$ and $b$ with weight $c$.

Cities are numbered from $1$ to $n$. The graph is connected. Multiple roads between the same pair of cities, and self-loops, are allowed.

Output

Output $m$ lines. The $i$-th line should contain forced, optional, or useless, the classification of the $i$-th road in the input.

Constraints

• $1 \le n \le 10^5$
• $n - 1 \le m \le 2 \times 10^5$
• $1 \le a, b \le n$
• $1 \le c \le 10^9$

Example 1

3 3
1 2 1
2 3 2
1 3 3

forced
forced
useless

Explanation

The unique MST uses the two lighter roads. The heaviest road can never appear.

Example 2

4 5
1 2 1
2 3 1
1 3 1
1 4 2
2 4 2

optional
optional
optional
optional
optional

Explanation

Any two of the weight-$1$ roads connect cities $1,2,3$, and either weight-$2$ road can finish the tree. No road is required in every MST, and none is useless.