카투스 변환

대학에서 캐롤라인은 카투스 그래프를 배우기 시작했다. 선생님은 학생들이 카투스의 정의를 제대로 이해했는지 확인하려고 다음 과제를 냈다.

정점 개수와 간선 개수가 같은 카투스 두 개가 주어진다. 다음 두 단계 연산을 최대 $15\,000$번 사용해서 첫 번째 카투스를 두 번째 카투스로 바꿀 수 있는지 판단하라.

• 첫 번째 카투스에서 임의의 간선 하나를 골라 제거한다. 이 단계 이후의 그래프는 카투스가 아닐 수도 있다.
• 첫 번째 그래프에 존재하지 않는 임의의 간선 하나를 추가하여, 그래프가 카투스가 되도록 만든다.

연산은 두 단계를 합쳐서 하나이므로, 매번 반드시 두 단계를 모두 수행해야 한다.

변환이 가능하다면 최대 $15\,000$번의 연산으로 가능하다는 것이 보장된다.

카투스는 연결된 무향 그래프이며, 모든 간선이 최대 하나의 단순 사이클에 속한다. 카투스에는 다중 간선과 자기 루프가 없다.

두 카투스가 같다는 것은 임의의 정점 쌍 $v$와 $u$ ($1 \le v < u \le n$)에 대해, 두 카투스 모두 간선 $(v, u)$를 갖거나 모두 갖지 않는다는 뜻이다.

첫 줄에 정수 $n$과 $m$이 주어진다 ($3 \le n \le 1000$, $n - 1 \le m \le \lfloor \frac{3(n - 1)}{2} \rfloor$). 두 값은 각각 카투스의 정점 개수와 간선 개수이다. 이어지는 $2 \cdot m$개의 줄에 정수 $u$와 $v$ ($1 \le u \ne v \le n$)가 한 쌍씩 주어지며, 이는 간선을 나타낸다. 처음 $m$개의 줄은 첫 번째 카투스의 간선이고, 나머지 $m$개의 줄은 두 번째 카투스의 간선이다.

첫 번째 카투스를 두 번째 카투스로 변환할 수 없으면 "NO"만 한 줄에 출력한다.

변환할 수 있으면 첫 줄에 "YES"를 출력한다. 둘째 줄에는 연산 횟수 $c$ ($0 \le c \le 15\,000$)를 출력한다. 이어지는 $c$개의 줄에는 정수 $w_1$, $w_2$, $w_3$, $w_4$ ($1 \le w_i \le n$)를 한 줄에 네 개씩 출력한다. $w_1$과 $w_2$는 제거하는 간선의 양 끝점이고, $w_3$과 $w_4$는 추가하는 간선의 양 끝점이다.