102933: [Atcoder]ABC293 D - Tying Rope

Problem Statement

There are $N$ ropes numbered $1$ through $N$. One end of each rope is painted red, and the other is painted blue.

You are going to perform $M$ operations of tying ropes. In the $i$-th operation, you tie the end of rope $A_i$ painted $B_i$ with the end of rope $C_i$ painted $D_i$, where R means red and B means blue. For each rope, an end with the same color is not tied multiple times.

Find the number of groups of connected ropes that form cycles, and the number of those that do not, after all the operations.

Here, a group of connected ropes $\lbrace v_0, v_1, \ldots, v_{x-1} \rbrace$ is said to form a cycle if one can rearrange the elements of $v$ so that, for each $0 \leq i < x$, rope $v_i$ is tied to rope $v_{(i+1) \bmod x}$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, C_i \leq 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$, and $C_i$ are integers.
• $B_i$ is R or B, and so is $D_i$.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $X$ and $Y$ in this order, separated by a space, where $X$ is the number of groups of connected ropes that form cycles, and $Y$ is the number of those that do not.

Sample Input 1

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

Sample Output 1

1 2

There are three groups of connected ropes: $\lbrace 1 \rbrace$, $\lbrace 2,4 \rbrace$, and $\lbrace 3,5 \rbrace$.

The group of ropes $\lbrace 3,5 \rbrace$ forms a cycle, while the groups of rope $\lbrace 1 \rbrace$ and ropes $\lbrace 2,4 \rbrace$ do not. Thus, $X = 1$ and $Y = 2$.

Sample Input 2

7 0

Sample Output 2

0 7

Sample Input 3

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

Sample Output 3

2 1

问题描述

有编号为1到N的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 \leq i < x$，绳子$v_i$与绳子$v_{(i+1) \bmod x}$系在一起。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, C_i \leq 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$也是如此。

输入

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

$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，其中X是形成循环的连通绳子的组数，Y是不形成循环的组数。

样例输入1

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

样例输出1

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。

样例输入2

7 0

样例输出2

0 7

样例输入3

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

样例输出3

2 1