Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

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

(Время: 2 сек. Память: 32 Мб Сложность: 53%)

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

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

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

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXT
13
1 2
2 3
IB
IV
IB
2

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ