Problem K
Underspecified Ultrametrics

Given a set of points $X$ with distances $d(u,v)$ betwen any $u,v \in X$, we say that $(X,d)$ is an ultrametric if the following properties are satisfied:

• $d(u,v) \geq 0$ for any two points $u,v$ with $d(u,v) = 0$ if and only if $u = v$

• $d(u,v) = d(v,u)$ for any two points $u,v$

• $d(u,v) \leq \max \{ d(u,w), d(w,v)\} $ for any three points $u,v,w$

That is, distances in an ultrametric satisfy a slightly stronger property than the usual triangle inequality $d(u,v) \leq d(u,w) + d(w,v)$.

You have measured distances between some pair of points from some set $X$ and start to wonder if you might be looking at an ultrametric. Write a program to help you determine if this is the case!

Explanation of Sample Case 4

The following matrix, whose rows and columns are indexed from $0$ to $4$, specifies distances that form an ultrametric and agrees with the distances given in the input for this case.

Input

The first line of input contains two integers $N$ ($3 \leq N \leq 100\, 000$) and $M$ ($0 \leq M \leq 400\, 000$) where $N$ is the number of points in the set $X$ and $M$ is the number of distances you have determined so far. The points are numbered from $0$ to $N-1$.

Then $M$ lines follow, each containing three integers $u,v,\ell $ ($0 \leq u < v < N$ and $1 \leq \ell \leq 10^9$) where $u,v$ are two points in $X$ and $\ell $ is the distance $d(u,v)$ you have determined between these points. No pair of points will have their distance specified on more than on line.

Output

Output possibly ultrametric if there is an ultrametric $(X,d')$ where the distances satisfy $d'(u,v) = d(u,v)$ for any $u,v \in X$ such that one of the $M$ given distances you have already determined is for the pair $(u,v)$. Otherwise, output the message not ultrametric.

3 3
0 1 5
0 2 7
1 2 7

possibly ultrametric

3 3
0 1 5
0 2 7
1 2 5

not ultrametric

5 5
0 1 10
1 2 11
2 3 12
3 4 13
0 4 12

not ultrametric

5 5
0 1 10
1 2 11
2 3 12
3 4 13
0 4 13

possibly ultrametric

7 5
0 1 3
4 5 1
0 2 1
1 2 3
4 6 10

possibly ultrametric