Олимпиадный тренинг

Задача . E. Путешествие по царству Снежной королевы

Задача

Темы: битмаски графы Перебор разделяй и властвуй *2800

Герда пустилась в путь по царству Снежной королевы.

Дорожная сеть, по которой направляется Герда, представляет собой n перекрёстков, соединённых m дорогами. Дороги пронумерованы числами от 1 до m. Снежная королева догадывалась, что Кая могут найти, и наложила на них могучее заклятие. Теперь погодные условия на дороге с номером i таковы, что в какой бы момент времени, не превосходящий i, Герда ни оказалась на ней, она выедет с неё только в момент времени i. Если же она ступит на дорогу позже, чем в момент времени i, она так и не сможет с неё выехать.

Герда выезжает в момент времени l с перекрёстка с номером s и едет во дворец Снежной королевы, расположенный на перекрёстке с номером t. Кроме того, в момент времени r + 1 Снежная королева возвращается в свой дворец и уже не пустит Герду внутрь, поэтому Герда должна добраться до дворца не позже, чем в момент времени r.

Вам требуется по заданной сети для каждого из q запросов l_i, r_i, s_i и t_i ответить, сможет ли Герда добраться до дворца Снежной королевы.

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

В первой строке входных данных находятся числа n, m и q (2 ≤ n ≤ 1000, 1 ≤ m, q ≤ 200 000) — количество перекрёстков в дорожной сети царства Снежной королевы, дорог в ней, случаев расположения Герды, дворца Снежной королевы и времён выезда Герды и возвращения Снежной королевы соответственно.

В i-й из следующих m строк дано описание дороги с номером i. Описание состоит из целых чисел v_i и u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — номеров перекрёстков, соединённых этой дорогой. По дороге можно добраться как из перекрёстка v_i на перекрёсток u_i, так и из перекрёстка u_i в перекрёсток v_i. Каждая пара перекрёстков может встречаться более одного раза, это значит, что между ними есть несколько разных дорог.

Затем следуют описания тестовых случаев. В каждой из следующих q строк содержатся четыре числа l_i, r_i, s_i и t_i (1 ≤ l_i ≤ r_i ≤ m, 1 ≤ s_i, t_i ≤ n, s_i ≠ t_i) — момент времени, когда Герда выезжает, самый поздний момент времени, когда она может приехать во дворец, номер перекрёстка, с которого выезжает Герда, и номер перекрёстка, на котором расположен дворец Снежной Королевы.

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

Для каждого тестового случая выведите «Yes» (без кавычек) или «No» (без кавычек) — сможет Герда добраться до дворца Снежной королевы или нет.

Примеры

№	Входные данные	Выходные данные
1	5 4 6 1 2 2 3 3 4 3 5 1 3 1 4 1 3 2 4 1 4 4 5 1 4 4 1 2 3 1 4 2 2 2 3	Yes Yes Yes No No Yes

time 1500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

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

Загруженные файлы

Нет