После революции в Берляндии новый диктатор столкнулся с неожиданной проблемой — страной надо как-то управлять. Диктатор является очень эффективным менеджером, однако не может раздавать приказы всему населению лично, поэтому он решил выбрать некоторое множество подконтрольных ему лидеров, которые и будут управлять людьми непосредственно. Однако оказалось, что лидерская эффективность может очень сильно варьироваться от человека к человеку, поэтому диктатор обратился за помощью к всемирно известным берляндским ученым. Ученые предложили инновационную идею — лидеры должны работать парами.
Граф взаимоотношений — некоторый неориентированный граф с вершинами, соответствующими людям. Путь называется простым, если вершины в нем не повторяются. В результате многодневных и очень дорогих исследований было выяснено, что пара людей обладает наиболее высокими лидерскими качествами, если между ними в графе взаимоотношений есть простой путь с нечетным количеством ребер. Ученые решили называть такие пары различных людей лидерскими. Спецслужбы выдали ученым граф взаимоотношений, так что дело осталось за малым — надо научиться отвечать диктатору, являются ли лидерскими заданные пары людей. Помогите ученым справиться с этой задачей.
Выходные данные
Для каждого запроса ученых в отдельной строке выведите «Yes», если между парой людей существует простой нечетный путь, иначе выведите «No».
Примечание
Пояснение к примеру:
1) Между вершинами 1 и 2 есть всего 2 различных простых пути: 1-3-2 и 1-4-2. Оба состоят из четного количества ребер.
2) Вершины 1 и 3 соединены ребром, поэтому простой нечетный путь для них: 1-3.
5) Вершины 1 и 5 находятся в разных компонентах связности, между ними нет ни одного пути.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 7
1 3
1 4
2 3
2 4
5 6
6 7
7 5
8
1 2
1 3
1 4
2 4
1 5
5 6
5 7
6 7
|
No
Yes
Yes
Yes
No
Yes
Yes
Yes
|