신장 트리의 차수

연결된 무방향 그래프가 주어진다. 정점은 $n$개, 간선은 $m$개이다. 모든 정점의 차수가 $\frac{n}{2}$ 이하인 신장 트리를 하나 찾아라.

정점의 차수는 그 정점에 연결된 간선의 개수이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정점의 수 $n$과 간선의 수 $m$이 주어진다 ($2 \le n \le 10^5$, $n-1 \le m \le 2 \times 10^5$).

이후 $m$개의 줄에 정수 $u_i$와 $v_i$가 주어진다 ($1 \le u_i, v_i \le n$). 이는 정점 $u_i$와 정점 $v_i$를 잇는 간선이 있다는 뜻이다. 자기 루프와 다중 간선이 있을 수 있다.

그래프는 연결되어 있다. 모든 테스트 케이스의 $n$ 합은 $5 \times 10^5$을 넘지 않고, $m$ 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 조건을 만족하는 신장 트리가 존재하면 한 줄에 "Yes"를 출력한다. 이어서 $n-1$개의 줄에 정수 $p_i$와 $q_i$를 공백으로 구분하여 출력한다. 이는 트리에 정점 $p_i$와 정점 $q_i$를 잇는 간선이 포함된다는 뜻이다.

조건을 만족하는 신장 트리가 없으면 한 줄에 "No"를 출력한다.

첫 번째 예제에서 신장 트리의 최대 차수는 3이다 (정점 1과 정점 4의 차수가 모두 3이다). $3 \le \frac{6}{2}$이므로 유효한 답이다.

두 번째 예제에서는 어떤 신장 트리를 골라도 차수가 2인 정점이 생긴다. $2 > \frac{3}{2}$이므로 유효한 답이 없다.