系绳子

题目描述

有 $N$ 根绳子，编号为 $1$ 到 $N$。每根绳子的一端涂成红色，另一端涂成蓝色。

你将执行 $M$ 次系绳操作。在第 $i$ 次操作中，将绳子 $A_i$ 涂成颜色 $B_i$ 的一端与绳子 $C_i$ 涂成颜色 $D_i$ 的一端系在一起，其中 R 表示红色，B 表示蓝色。对于每根绳子，同一种颜色的端不会被多次系在一起。

求所有操作结束后，形成环的连通绳组个数，以及不形成环的连通绳组个数。

这里，一组连通的绳子 $\lbrace v_0, v_1, \ldots, v_{x-1} \rbrace$ 被称为形成环，如果可以将 $v$ 的元素重新排列，使得对每个 $0 \le i \lt x$，绳子 $v_i$ 都与绳子 $v_{(i+1) \bmod x}$ 系在一起。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $B_1$ $C_1$ $D_1$
$A_2$ $B_2$ $C_2$ $D_2$
$\vdots$
$A_M$ $B_M$ $C_M$ $D_M$

输出格式

按顺序输出形成环的连通绳组个数 $X$ 和不形成环的连通绳组个数 $Y$，以空格隔开。

样例

5 3
3 R 5 B
5 R 3 B
4 R 2 B

1 2

共有三个连通绳组：$\lbrace 1 \rbrace$、$\lbrace 2, 4 \rbrace$ 和 $\lbrace 3, 5 \rbrace$。

绳组 $\lbrace 3, 5 \rbrace$ 形成环，而绳组 $\lbrace 1 \rbrace$ 和 $\lbrace 2, 4 \rbrace$ 不形成环。因此 $X = 1$、$Y = 2$。

7 0

0 7

7 6
5 R 3 R
7 R 4 R
4 B 1 R
2 R 3 B
2 B 5 B
1 B 7 B

2 1

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i, C_i \le N$
• $(A_i, B_i) \neq (A_j, B_j)$，$(C_i, D_i) \neq (C_j, D_j)$（$i \neq j$）
• $(A_i, B_i) \neq (C_j, D_j)$
• $N, M, A_i, C_i$ 均为整数
• $B_i$ 是 R 或 B，$D_i$ 也是 R 或 B