Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fighting Over a Duster

By curly_braces · Limits 1s, 512 MB

There are two sections in Toph school and college named section A and section B. Recently the students of the sections engaged into a fight over a duster. Since this is violation of rules, the authority decided to rusticate some students permanently. So, the authority asked the teachers to vote for students who should stay and who should leave based on their past behavioral record. Based on the votes, authority will take the decision.

However, teachers are biased. Every teacher takes class in only one section. No teacher wants anyone of his/her section to leave. So each teacher votes for one student of his/her section to stay, and one student from the other section to leave. More formally, each teacher chooses exactly two students. One from his/her own section (to stay), and one from the other section (to leave).

After receiving all the votes, the authority will select some students to leave. A teacher will be happy if his/her vote turned into reality (his/her chosen student from his/her own section stayed and his/her chosen student from other section left).

The authority has chosen you for the task. You will have to choose a subset of students to leave in such a way that maximum possible number of teachers are happy.


Input starts with an integer $T(0 < T \leq 50)$, denoting number of test cases.

Each test case starts with 3 integers, $a (0 < a \leq 100), b(0 < b \leq 100)$ and $n (0 \leq n \leq 500)$, number of students in section A, students in section B and number of teachers who voted, respectively.

Every student in section A has distinct ID between $1$ and $a$, similarly every student in section B has a distinct ID between $1$ and $b$.

Next $n$ lines describe the votes of the teachers. Each line starts with a character containing which section the teacher takes class on. ‘A’ for section A and ‘B’ for section B. Then comes two integers, $p$ and $q$ meaning he/she wants student with ID $p$ from his section to stay and student from with ID $q$ from the other section to leave.

It is guaranteed that vote of every teacher is valid, there is one student in his/her section with ID $p$, and one student in the other section with ID $q$.

Subtask Constraints

Subtask 1 (10% of points)

$a + b \leq 8$
$n \leq 8$

Subtask 2(20% of points)

$a + b \leq 32$
$n \leq 16$

Subtask 3 (40% of points)

$a + b \leq 32$
$n \leq 32$

Subtask 4 (100% of points)

Original Constraints.


For each test case, print an integer denoting the maximum number of happy teachers.


5 5 3
B 1 2
A 2 4
A 1 1
2 2 4
A 1 1
B 1 2
A 2 2
B 2 1



    50% Solution Ratio

    YouKnowWhoEarliest, 3w ago

    YouKnowWhoFastest, 0.0s

    YouKnowWhoLightest, 655 kB

    YouKnowWhoShortest, 1822B


    Login to submit


    Subtask 1: Generate all possible subset of students. For all possible subset of students, find what’...