Жизнь цвета индиго

Мальчику Севе очень нравится цвет индиго (это такой темно-синий цвет). Сева всячески старается окружить себя вещами этого цвета.

Скоро Новый год, и Сева решил изготовить гирлянду с лампочками, чтобы украсить ей свою комнату. Он купил n патронов для лампочек и соединил (n−1)-им проводом так, что в гирлянде не образовалось ни одного замкнутого контура. Его гирлянда, таким образом, с точки зрения математики, представляет собой дерево. Для того чтобы гирлянда была готова, осталось совсем немного надо только добавить провод для подключения гирлянды в электрическую сеть и вкрутить разноцветные лампочки в патроны.

У Севы есть лампочки трех разных цветов: синего, фиолетового и индиго. При этом, в некоторые патроны из соображений красоты нельзя устанавливать лампочки определенных цветов. Также, из соображений красоты, в гирлянде не должно быть двух лампочек одного цвета, напрямую соединенных проводом. Разумеется, Сева хочет, чтобы в гирлянде было как можно больше лампочек его любимого цвета.

Помогите Севе. Напишите программу, которая найдет максимальное количество лампочек цвета индиго, которые можно установить в собранную Севой гирлянду.

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число n количество патронов для лампочек в Севиной гирлянде (1 ≤ n ≤ 50000). Последующие (n−1) строка содержат каждая по два числа: u_i и v_i (1 ≤ u_i, v_i ≤ n) – номера патронов, соединенных соответствующим проводом.

Далее следуют n строк с описанием патронов. Каждая из них не пуста и состоит не более, чем из трех различных символов «I», «B» или «V». i-ая из этих строк описывает i-ый патрон, а именно: если она содержит символ «I», то в i-ый патрон можно устанавливать лампочку цвета индиго, «B» - можно устанавливать лампочку синего цвета, «V» - можно устанавливать лампочку фиолетового цвета.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное число: ответ на задачу. Если же при наложенных ограничениях Севе вообще не удастся собрать гирлянду, выведите число −1.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]