Вам задан двудольный граф: первая доля графа содержит \(n_1\) вершин, вторая — \(n_2\) вершин, а также в графе \(m\) ребер. Граф может содержать кратные ребра.
Первоначально, все ребра графа бесцветные. Каждое ребро вы можете либо оставить бесцветным (это бесплатно), либо покрасить в красный (стоимость данного действия \(r\) монет), либо покрасить в синий (за \(b\) монет). Никакое ребро не может быть покрашено в оба цвета одновременно.
Также в графе вершины разбиваются на три типа — бесцветные, красные и синие. Цветные вершины добавляют дополнительные ограничения на раскраску ребер:
- у каждой красной вершины количество смежных с ней красных ребер должно быть строго больше, чем смежных с ней синих ребер;
- у каждой синей вершины количество смежных с ней синих ребер должно быть строго больше, чем смежных с ней красных ребер.
Бесцветные вершины не накладывают никаких ограничений.
Ваша задача — раскрасить некоторые (возможно, никакие) ребра так, чтобы выполнялись заданные ограничения, и среди всех возможных раскрасок выбрать такую, суммарная стоимость которой минимальна.
Выходные данные
Если не существует раскраски ребер, которая удовлетворяет всем заданным ограничениям, — выведите \(-1\).
Иначе, выведите число \(c\), обозначающее минимальную суммарную стоимость раскраски, и строку из \(m\) символов. \(i\)-й символ должен быть U, если \(i\)-е ребро осталось бесцветным, R, если \(i\)-е ребро покрашено в красный, или B, если \(i\)-е ребро покрашено в синий. Если существует несколько оптимальных раскрасок — выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 6 10 15
RRB
UB
3 2
2 2
1 2
1 1
2 1
1 1
|
35
BUURRU
|
|
2
|
3 1 3 4 5
RRR
B
2 1
1 1
3 1
|
-1
|
|
3
|
3 1 3 4 5
URU
B
2 1
1 1
3 1
|
14
RBB
|