eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дорожные работы

Дорожные работы

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В республике Икс издавна действует двухпартийная система. Каждый год граждане, имеющие избирательные права, голосуют, какой партии они больше доверяют - партии Мошенников или партии Грабителей, и в течение этого года вся реальная власть сосредоточена в руках избранной партии.

В последние M лет между партиями разразилась нешуточная война по перестройке дорожной сети республики "под себя". Партия Мошенников стремится построить как можно больше государственных дорог, чтобы прикарманить побольше бюджетных денег на их "обслуживание", а партия Грабителей стремится сделать платными как можно большее число дорог. Движение на всех дорогах республики Икс двустороннее.

Известно, что в течение одного года правления партии Мошенников удавалось построить ровно одну новую дорогу (которая поначалу является бесплатной), а партии Грабителей - ввести плату за проезд по одной из бесплатных на текущий момент дорог (при этом деньги на содержание этой дороги выделяются уже не из бюджета, а из средств, вырученных за проезд).

Президент республики, в настоящее время не имеющий реального политического влияния, решил привлечь внимание общественности к проблеме дорог. Он назвал дорожную сеть удобной (для простых граждан), если из любого города можно доехать до любого, используя только бесплатные дороги, но при этом количество бесплатных дорог (а, соответственно, и бюджетные средства на их содержание, полученные сбором налогов с граждан республики) - минимально возможное.

Вам поручено написать программу, которая определяет, была ли дорожная сеть удобной по завершении i-го года "дорожной войны".

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

В первой строке ввода заданы два числа - N (1N1000), число городов в республике Икс, и M (1M100000), продолжительность порядком затянувшейся "дорожной войны". Далее следуют M строк, первый символ каждой из которых - это F, если в данный год у власти была партия Мошенников, и R - если партия Грабителей, а далее в строке следуют два числа - номера городов u_i и v_i - пара городов, дорога между которыми стала объектом пристального внимания соответствующей партии (была построена новая дорога, если у власти была партия Мошенников, и одна из существующих дорог была сделана платной, если у власти была партия Грабителей). Вполне возможна ситуация, когда между двумя городами окажется более одной дороги, или будет построена дорога из города в себя - мало ли, что там удумает партия Мошенников.

Гарантируется, что входные данные корректны, то есть, все числа u_i и v_i лежат в пределах от 1 до N, и если известно, что в какой-то год дорога между двумя городами была сделана платной, то это значит, что перед началом года была хотя бы одна бесплатная дорога между этими городами.

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

Для каждого года выведите в отдельной строке YES, если дорожная сеть по завершении соответствующего года была удобной, и NO в противном случае.

Пример

Входные данные #1
4 8
F 1 2
F 1 3
R 1 3
F 2 3
F 3 4
F 1 3
R 1 3
F 1 1
Выходные данные #1
NO
NO
NO
NO
YES
NO
YES
NO
Автор S.Kopeliovich, A.Lopatin