В одной организации после модернизации оборудования осталось ненужное
устройство, и его подарили университету для лабораторных работ. Устройство
имеет два интерфейса: типа A и
типа B, к каждому из которых
можно подключить один периферийный блок с таким же интерфейсом.
К аппарату прилагается
набор блоков с интерфейсами типа A
и B. Блоки можно подключать как
поодиночке, так и сразу по два — один типа A
и один типа B. К сожалению,
допустимо использовать не все возможные пары блоков — при подключении некоторых
пар устройство может сгореть.
Как известно, студенты на
лабораторных работах далеко не всегда строго следуют инструкциям. Поэтому было
принято решение некоторые блоки убрать (и выдавать их только по особой
надобности). Требуется определить, какие из блоков нужно убрать, чтобы среди
оставшихся больше не было опасных пар, а число убранных блоков было
минимальным.
В первой строке входного файла находятся
три целых числа, N, M и K
(1 <= N, M <= 100, 1 <= K <= 10 000), где N — число блоков типа A,
M — число блоков типа B, K
— количество опасных пар. В следующих K
строках перечислены опасные пары блоков — каждая строка содержит два
разделённых пробелом числа ai
и bi, где ai — номер блока типа A, bi
— номер блока типа B.
В первой строке выходного файла выведите
минимальное число блоков, которые требуется убрать. В следующих строках
перечислите блоки, которые требуется убрать, каждый блок описывается следующим
образом: сначала идёт тип блока — буква A
или B, затем (без пробела) — его
номер. Если задача имеет несколько правильных решений, выведите любое из них.
Пример
|
STDIN
|
STDOUT
|
|
3 4 7
1 1
1 2
2 1
2 3
2 4
3 1
3 2
|
3
B1
A2
B2
|
