← 返回题目列表

AtCoder · abc293_d

G. 绑绳

中文机器翻译题面 查看原题

分数: 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 R or 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