Задача №114757. Трудная задача
Дан неориентированный граф, состоящий из \(3n\) вершин и ровно \(3n\) рёбер. Независимым множеством назовём множество вершин такое, что между любыми двумя вершинами в нём нет ребра.
Вам интересно, можно ли найти в данном графе независимое множество, состоящее из \(n\) вершин.
В первой строке задано целое число \(n\) (\(1 \leq n \leq 100\,000\)).
В следующих \(3n\) строках задано описание рёбер графа. Каждое ребро задано парой целых чисел \(u_i, v_i\) (\(1 \leq u_i, v_i \leq 3n\)) — номерами вершин, которые оно соединяет.
Гарантируется, что в графе нет петель и кратных рёбер.
В случае, если в графе нет независимого множества размера \(n\), выведите « No ». В противном случае в первой строке выведите « Yes », а во второй — \(n\) различных целых чисел — номера вершин в независимом множестве.
Если существует несколько решений, выведите любое из них.
1 1 2 2 3 3 1
Yes 1
2 1 2 2 3 3 4 4 1 1 3 2 4
Yes 1 5