Candy

Problem Source

SCOI 2011

Problem Description

There are $N$ children in the kindergarten. Teacher $\text{lxhgww}$ now wants to distribute candies to these children; every child must receive at least one candy. But the children are jealous and always make some demands. For example, Xiao Ming does not want Xiao Hong to get more candies than him. So while distributing candies, $\text{lxhgww}$ must satisfy $K$ demands from the children. The kindergarten's candies are always limited, and $\text{lxhgww}$ wants to know the minimum number of candies he must prepare so that every child gets at least one candy and all the children's demands are satisfied.

Input Format

The first line of the input contains two integers $N, K$ ($1 \leq N, K \leq 10^5$). The next $K$ lines describe the relations that must be satisfied; each line contains three numbers $X, A, B$ ($1 \leq A, B \leq N$):

• If $X = 1$, the number of candies child $A$ gets must equal the number child $B$ gets.
• If $X = 2$, the number child $A$ gets must be strictly less than the number child $B$ gets.
• If $X = 3$, the number child $A$ gets must be no less than the number child $B$ gets.
• If $X = 4$, the number child $A$ gets must be strictly greater than the number child $B$ gets.
• If $X = 5$, the number child $A$ gets must be no greater than the number child $B$ gets.

Output Format

Output one line: the minimum number of candies teacher $\text{lxhgww}$ must prepare. If it is impossible to satisfy all the children's demands, output $-1$.

Sample Input

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

Sample Output

11

Constraints

• $1 \leq N, K \leq 10^5$
• $1 \leq A, B \leq N$