trang chủ / đề bài / icpc21_bt_c

Trại giao lưu

Đề bài

Mô tả

Ở Gakuentoshi, mỗi người đều có một kỹ năng riêng của mình. Uiharu và Shirai tổ chức một buổi giao lưu để các bạn dạy kỹ năng cho nhau và làm quen với bạn mới. Uiharu và các bạn của cô là đội Đỏ, Shirai và các bạn của cô là đội Trắng.

Mỗi người trong đội Đỏ sẽ chọn một thành viên của đội Trắng làm học trò, và mỗi người trong đội Trắng sẽ chọn một thành viên của đội Đỏ làm học trò. Mọi người đều chọn một học trò, và mỗi người chỉ được làm học trò của đúng một người.

Đầu tiên, đội Đỏ dạy cho học trò của mình kỹ năng riêng của họ, đồng thời đội Trắng cũng dạy cho học trò của mình kỹ năng riêng của họ. Lúc này mỗi người đã học được một kỹ năng mới. Sau đó, mỗi người lại dạy cho học trò của mình kỹ năng mới vừa học được. Quá trình này tiếp tục cho đến khi không ai học được kỹ năng mới nữa.

Mỗi đội có N người, và đã có M người chọn xong học trò. Uiharu muốn biết còn bao nhiêu cách chọn để cuối cùng mỗi người đều học được kỹ năng của tất cả những người tham gia. Hai cách được coi là khác nhau nếu có một người chọn học trò khác nhau.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên T là số bộ dữ liệu.
  • Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa hai số nguyên N và M: mỗi đội có N người và đã có M người chọn học trò.
  • M dòng tiếp theo, dòng thứ i chứa một chữ cái Ci và hai số nguyên ui, vi. Ci là R hoặc W: R nghĩa là thành viên thứ ui của đội Đỏ chọn thành viên thứ vi của đội Trắng làm học trò; W nghĩa là thành viên thứ ui của đội Trắng chọn thành viên thứ vi của đội Đỏ làm học trò. Mỗi người xuất hiện tối đa một lần với vai trò người chọn.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số cách chọn để mỗi người đều học được kỹ năng của tất cả những người tham gia.

Ràng buộc

  • 1≤T≤100.
  • 1≤N≤7.
  • 0≤M≤2N.
  • Ci là R hoặc W.
  • 1≤ui,vi≤N.

Ví dụ

Input Output Giải thích
2
1 1
R 1 1
3 2
R 3 1
W 2 2
1
1
Bộ thứ nhất: thành viên Trắng duy nhất buộc phải chọn thành viên Đỏ duy nhất.
1
2 0
2 Đỏ 1 có 2 cách chọn học trò, sau đó mọi lựa chọn còn lại bị buộc để bốn người tạo thành một vòng truyền kỹ năng duy nhất.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0