정점이 개이고 간선이 개인 무방향 단순 연결 그래프가 주어진다. 정점에는 부터 까지 번호가 붙어 있다.
모든 간선을 정확히 두 번씩 지나는 닫힌 보행을 구하여라. 같은 간선을 연속으로 지나서는 안 되며, 마지막에 지나는 간선과 처음에 지나는 간선도 서로 달라야 한다.
보행의 정의
그래프에서 보행이란, 정점의 열 에서 연속한 두 정점 과 를 잇는 간선이 항상 존재하는 것을 말한다. 보행에서는 같은 정점이나 간선을 여러 번 방문하거나 지나도 된다.
간선을 지나는 방향은 제한하지 않는다. 조건을 만족하는 닫힌 보행이 없다면 없다고 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 닫힌 보행이 없다면 한 줄에 NO를 출력한다.
존재한다면 첫째 줄에 YES를 출력한다. 둘째 줄에는 방문하는 정점의 번호 을 공백으로 구분하여 출력한다.
첫 번째 테스트 케이스의 한 답은 이다. 두 번째 테스트 케이스에는 조건을 만족하는 닫힌 보행이 없다.
시작 정점과 마지막 정점이 같은 보행, 즉 인 보행을 닫힌 보행이라고 한다.
는 테스트 케이스의 수이다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
번 간선은 정점 와 를 잇는다 ().
이어야 한다. 각 ()에 대해 과 를 잇는 간선이 있어야 하며, 이 간선들을 순서대로 지나는 보행이 문제의 모든 조건을 만족해야 한다. 시작 정점은 자유롭게 정할 수 있다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.
추가적인 제약이 없다.
