일방통행 도로

ACM 왕국에는 도시 $N$개가 있고, 양방향 도로 $M$개가 도시를 잇는다. 도로망은 연결되어 있어서 어느 도시에서 출발하든 도로를 따라 다른 모든 도시에 갈 수 있다. 정부는 모든 도로를 일방통행으로 바꾸려 한다. 방향을 정한 뒤에도 어느 도시에서든 다른 모든 도시로 갈 수 있어야 한다. 그런 배정이 있는지 판정하고, 있으면 출력 항목이 정한 배정을 출력한다.

첫 줄에 테스트 케이스의 수 $T$ ($0 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$ ($1 \le N \le 50$)과 $M$ ($1 \le M \le N(N-1)/2$)이 주어진다. 이어지는 $M$개의 줄에는 두 정수 $X$와 $Y$ ($1 \le X, Y \le N$, $X \ne Y$)가 주어지며, 도시 $X$와 도시 $Y$를 잇는 도로를 뜻한다. 같은 도시 쌍을 잇는 도로는 많아야 하나이고, 모든 테스트 케이스의 도로망은 연결되어 있다.

각 테스트 케이스마다, 조건을 만족하는 배정이 없으면 한 줄에 NO를 출력한다. 있으면 첫 줄에 YES를 출력하고, 이어서 각 도로의 방향을 $M$개의 줄에 출력한다. $i$번째 줄에는 입력의 $i$번째 도로의 출발 도시와 도착 도시를 차례로 쓴다.

가능한 배정이 여럿일 수 있으므로 그중 하나만 정답으로 인정한다. 그 배정은 다음과 같이 만든다. 도시 1에서 깊이 우선 탐색을 시작한다. 탐색이 한 도시를 떠날 때는 아직 방문하지 않은 이웃 도시 중 번호가 가장 작은 곳으로 가고, 현재 도시의 이웃을 모두 방문했으면 되돌아간다. 탐색이 어떤 도시에 처음 도착할 때 지나간 도로는 떠난 도시에서 도착한 도시로 향하게 한다. 나머지 도로는 두 끝 도시 중 탐색이 나중에 방문한 도시에서 먼저 방문한 도시로 향하게 한다. 조건을 만족하는 배정이 하나라도 있으면 이렇게 만든 배정도 조건을 만족한다.