Для неориентированного графа \(G\) назовем порядком соседей упорядоченный список всех соседей вершины для каждой из вершин \(G\). Рассмотрим некоторый порядок соседей в графе \(G\) и три вершины \(u\), \(v\) и \(w\) такие, что \(v\) является соседом \(u\) и \(w\). Мы будет использовать запись \(u <_{v} w\), если \(u\) стоит после \(w\) в списке соседей вершины \(v\).
Порядок соседей называется хорошим, если для каждого простого цикла \(v_1, v_2, \ldots, v_c\) графа выполняется одно из следующих условий:
- \(v_1 <_{v_2} v_3, v_2 <_{v_3} v_4, \ldots, v_{c-2} <_{v_{c-1}} v_c, v_{c-1} <_{v_c} v_1, v_c <_{v_1} v_2\),
- \(v_1 >_{v_2} v_3, v_2 >_{v_3} v_4, \ldots, v_{c-2} >_{v_{c-1}} v_c, v_{c-1} >_{v_c} v_1, v_c >_{v_1} v_2\).
Для заданного графа \(G\) определите, существует ли для него порядок хороших соседей, и постройте его, если он существует.
Выходные данные
Для каждого набора входных данных выведите одну строку с «YES», если граф допускает хороший порядок соседей, иначе выведите одну строку с «NO». Вы можете печатать каждую букву в любом регистре (верхнем или нижнем).
Если ответ «YES», дополнительно выведите \(n\) строк, описывающих порядок хороших соседей. В \(i\)-й строке выведите соседей вершины \(i\) по порядку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 6
0 1
0 2
1 2
2 3
3 4
4 1
2 1
0 1
6 10
0 1
2 0
0 3
0 4
1 2
1 4
2 3
2 5
3 5
4 5
|
YES
1 2
4 2 0
0 1 3
2 4
3 1
YES
1
0
NO
|