Дан простой неориентированный граф с \(n\) вершинами и \(m\) ребрами. Граф может не быть связным. Вершины графа пронумерованы от \(1\) до \(n\).
Граф-рыба — это граф, содержащий простой цикл с особой вершиной \(u\), принадлежащей циклу. Помимо ребер цикла, у графа должно быть ровно \(2\) дополнительных ребра. Оба ребра должны быть соединены с вершиной \(u\), но не должны быть соединены с любой другой вершиной цикла.
Определите, содержит ли данный граф подграф-рыбу, и если да, найдите любой такой подграф.
В этой задаче подграф определяется как граф, полученный путем выбора любого подмножества ребер исходного графа.
Визуализация примера 1. Красные ребра образуют один из возможных подграфов, который является графом-рыбой. Выходные данные
Для каждого набора входных данных выведите «YES», если граф содержит подграф-рыбу, в противном случае выведите «NO». Если ответ «YES», на следующих строках выведите описание подграфа.
Первая строка описания содержит одно целое число \(k\) — количество ребер подграфа.
В следующих \(k\) строках выведите ребра выбранного подграфа. Каждая из \(k\) строк должна содержать два целых числа \(u\) и \(v\) (\(1\le u, v\le n\), \(u\neq v\)) — ребро между \(u\) и \(v\) принадлежит подграфу. Порядок, в котором выводятся \(u\) и \(v\), не имеет значения, если эти две вершины соединены ребром в исходном графе. Порядок вывода ребер не имеет значения, если полученный подграф является графом-рыбой.
Если есть несколько решений, выведите любое.
Примечание
В первом примере возможный допустимый подграф содержит цикл \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1\). Особой вершиной этого цикла является вершина \(4\). Два дополнительных ребра \(4 - 5\) и \(4 - 6\) оба соединены с \(4\), образуя граф-рыбу.
Во втором примере возможный допустимый подграф содержит цикл \(1 \rightarrow 3 \rightarrow 4 \rightarrow 1\). Особой вершиной этого цикла является вершина \(3\). Два дополнительных ребра \(3 - 2\) и \(3 - 5\) оба соединены с \(3\), образуя граф-рыбу.
В последнем примере можно доказать, что у графа нет подграфа-рыбы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7 8
1 2
2 3
3 4
4 1
4 5
4 6
4 2
6 7
7 7
6 7
1 2
2 3
3 4
4 1
1 3
3 5
4 4
1 3
3 4
4 1
1 2
|
YES
6
5 4
6 4
4 3
1 4
2 1
3 2
YES
5
5 3
2 3
3 1
4 3
1 4
NO
|