Description

There are $N$ children in a kindergarten. Teacher $\text{lxhgww}$ wants to distribute candies to them, and every child must receive at least one candy. However, the children can be jealous and may raise some requests. For example, Xiao Ming does not want Xiao Hong to receive more candies than he does. Therefore, when distributing candies, $\text{lxhgww}$ needs to satisfy $K$ requests from the children. Since the total number of candies is limited, $\text{lxhgww}$ wants to know the minimum number of candies he needs to prepare so that every child receives candies and all requests are satisfied.

Input Format

The first line contains two integers $N, K$. The next $K$ lines each contain $3$ integers $X, A, B$, describing a request from the children.

• If $X=1$, the $A$-th child must receive the same number of candies as the $B$-th child.
• If $X=2$, the $A$-th child must receive fewer candies than the $B$-th child.
• If $X=3$, the $A$-th child must receive no fewer candies than the $B$-th child.
• If $X=4$, the $A$-th child must receive more candies than the $B$-th child.
• If $X=5$, the $A$-th child must receive no more candies than the $B$-th child.

Output Format

Output a single integer: the minimum number of candies $\text{lxhgww}$ needs to prepare. If it is impossible to satisfy all the requests, output $-1$.

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

11

Hint

For $30\%$ of the testdata, $N \leq 100$.

For $100\%$ of the testdata, $1 \leq N, K \leq 10^5$, $1 \leq X \leq 5$, $1 \leq A, B \leq N$.

$\text{upd 2022.7.6}$: Added $21$ sets of Hack testdata.

Translated by ChatGPT 5