Проверка, является ли граф «эффективным»
Дан неориентированный граф с
v вершинами и e рёбрами. Нужно определить, эффективен ли он. Граф считается «эффективным», если из любой его вершины можно добраться до любой другой, используя не более двух рёбер.Входные данные
В первой строке содержатся два целых числа
v (1 ≤ v ≤ 100) и e (1 ≤ e ≤ 10 000).В следующих
e строках записаны пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), которые обозначают ребро между v1 и v2.Выходные данные
Программа должна вывести
Yes, если граф является «эффективным», и No — в противном случае.Примеры
Входные данные | Выходные данные |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
Пояснение
- Вершина 4 не связана с остальными, поэтому невозможно добраться от неё до других (или наоборот) за два ребра.
- Из любой вершины можно попасть в любую другую, используя не более двух рёбер.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB