题目内容

计量室要对 $p$ 个样品的整数量值 $x_1,x_2,\ldots,x_p$ 做交叉核对。仪器打出 $e$ 条记录，每条只可能是下面两种之一：

• D $u$ $v$ $d$：表示差关系 $x_u-x_v=d$
• S $u$ $v$ $s$：表示和关系 $x_u+x_v=s$

量值必须是整数，可正可负可为零。请先判断这 $e$ 条记录有没有一组整数解；若有，再问至少要实测多少个样品的量值，才能把全部 $p$ 个量值都唯一定下来。一条记录里的两个下标可以相同。

输入描述

第一行两个整数 $p$ 和 $e$（$1\le p\le 100000$，$0\le e\le 100000$），表示样品数与记录数。

接下来 $e$ 行，每行一个大写字母 D 或 S，随后三个整数 $u,v,w$（$1\le u,v\le p$，$|w|\le 1000000000$）。字母为 D 时表示 $x_u-x_v=w$，为 S 时表示 $x_u+x_v=w$。

输出描述

第一行输出 YES 或 NO，表示是否存在整数解。

第二行：若第一行是 YES，输出最少实测个数（可以为 0，表示记录本身已经唯一确定全部量值）；若第一行是 NO，输出 -1。

样例1

输入

2 2
S 1 2 8
D 1 2 2

输出

YES
0

说明

$x_1+x_2=8$ 且 $x_1-x_2=2$，解得 $x_1=5$，$x_2=3$，已经唯一，不必再测。

样例2

输入

1 1
S 1 1 5

输出

NO
-1

说明

$2x_1=5$，不是整数，无解。

样例3

输入

3 2
D 1 2 1
D 2 3 1

输出

YES
1

说明

只有差关系，三个量由一个自由变量决定，实测任意一个即可推出其余。

数据范围

• $1\le p\le 100000$
• $0\le e\le 100000$
• $1\le u,v\le p$
• $|w|\le 1000000000$
• 线索类型仅为 D 或 S
• 所有编号与关系值均为整数