/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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, D_i は
RかBのいずれか
入力
入力は以下の形式で標準入力から与えられる。
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 の 3 つです。
ロープ \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
Score : 400 points
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
RorB, 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