잭의 양말

잭은 과학자입니다. 그래서 매일 무엇을 입는지에 크게 신경 쓰지 않습니다. 그는 여섯 가지가 넘는 색 이름을 알지 못하고, 미묘하게 다른 색조를 잘 구분하지도 못합니다. 오늘 잭은 학회에 가려고 하는데, 세탁기에서 짝이 맞지 않은 양말 한 무더기를 꺼내 짝을 지어야 합니다.

잭은 두 양말이 서로 비슷해 보이는지 판단할 수 있고, 비슷해 보이는 두 양말만 한 켤레로 묶으려 합니다. 그런데 "비슷함" 관계가 반드시 추이적이지는 않습니다. 예를 들어 잭에게 양말 A가 B와 비슷하고 B가 C와 비슷해 보이더라도, 잭은 A와 C를 구분하여 서로 비슷하지 않다고 여길 수 있습니다.

잭은 모든 양말을, 각 켤레가 서로 비슷한 두 양말로 이루어지도록 짝짓는 방법이 정확히 한 가지뿐인지 알고 싶어 합니다. 이를 판정하고, 유일한 짝짓기가 존재하면 그 짝짓기를 출력하는 프로그램을 작성하세요.

첫째 줄에 테스트 케이스의 수를 나타내는 양의 정수 $Z \le 50$ 이 주어집니다. 이어서 $Z$ 개의 테스트 케이스가 주어집니다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$ 과 $m$ 이 공백 하나로 구분되어 주어집니다 ($1 \le n \le 1000$, $0 \le m \le 10000$). $n$ 은 짝수이며 양말의 개수입니다. 양말에는 $1$ 부터 $n$ 까지 번호가 매겨져 있습니다. 이어지는 $m$ 개의 줄에는 각각 서로 다른 두 정수 $a_i$ 와 $b_i$ ($a_i \ne b_i$) 가 공백 하나로 구분되어 주어지며, 이는 양말 $a_i$ 와 $b_i$ 가 서로 비슷함을 뜻합니다. 각 비슷함 쌍은 정확히 한 번씩만 나열됩니다. 즉 $(a_i, b_i)$ 가 나타나면 이후에 $(a_i, b_i)$ 나 $(b_i, a_i)$ 는 다시 나타나지 않습니다.

각 테스트 케이스마다, 모든 양말을 서로 비슷한 두 양말끼리 짝짓는 방법이 정확히 한 가지 존재하는지 판정하세요.

그러한 짝짓기가 존재하지 않거나 두 가지 이상 존재하면, NO 만 적힌 한 줄을 출력합니다.

정확히 한 가지 짝짓기만 존재하면, 첫째 줄에 YES 를 출력하고, 이어서 그 유일한 짝짓기를 나타내는 $n/2$ 개의 줄을 출력합니다. 각 줄에는 한 켤레 $c\ d$ 를 $c < d$ 가 되도록 출력하며, 켤레들은 첫 번째 원소 기준 오름차순으로 정렬해야 합니다. 즉 연속한 두 켤레 $(c, d)$ 와 $(e, f)$ 에 대해 항상 $c < e$ 여야 합니다.