分数: 400 点
问题陈述
有 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}.
约束
- 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 is
RorB,也是如此 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