Score : $400$ points

问题描述

设有 $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 \leq i < x$，绳子 $v_i$ 与绳子 $v_{(i+1) \bmod x}$ 打结，则称其形成了一个循环。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:12:40