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