인터넷 문제

Lisa와 Sarah는 거대한 음모를 폭로한 뒤 부패한 정부를 피해 도망치는 중이다. 둘이 함께 있으면 둘 다 붙잡힐 위험이 너무 크기 때문에, 두 사람은 인터넷으로 연락하기로 했다. 하지만 평범한 인터넷은 충분히 안전하지 않아서, 둘은 다크 웹을 통해 비밀 메시지를 주고받는다.

다크 웹에서 모든 메시지는 목적지에 도달할 때까지 여러 서버를 거치는 길고 복잡한 경로를 지날 수 있으며, 같은 서버를 여러 번 지나갈 수도 있다. 덕분에 메시지를 추적하기가 훨씬 어려워진다.

그래도 Lisa는 여전히 걱정된다. 정부가 이미 다크 웹의 서버 하나를 해킹했다면 어떡하지? 해킹된 서버가 요충지에 있다면, 어떤 경로로 메시지를 보내든 Lisa가 Sarah에게 보내는 모든 메시지를 가로챌 수 있다.

Lisa가 이 인터넷 문제를 해결하도록 도와주자!

다크 웹은 1번부터 n번까지 번호가 붙은 n개의 서버로 이루어진다. 서버들은 m개의 네트워크 링크로 연결된다. 링크에는 방향이 있다. 한 서버가 다른 서버로 메시지를 전송할 수 있어도 반대 방향으로는 전송하지 못할 수 있다. Lisa는 서버 1에, Sarah는 서버 n에 연결되어 있다. Lisa가 Sarah에게 메시지를 보내고 싶을 때마다 메시지의 경로를 하나 고른다. 경로는 서버 1에서 서버 n으로 가는 연속된 네트워크 링크의 나열이다. 경로는 각 서버를 여러 번 지나갈 수 있다.

정부는 Lisa가 Sarah에게 보내는 메시지를 가로채려 한다. 정부는 서버 하나를 해킹해서 그 서버를 지나는 모든 메시지를 기록할 수 있다. 정부는 Lisa가 Sarah에게 보내는 모든 메시지를 정확히 한 번씩 보기를 원한다. ("적어도 한 번"은 그들의 모든 계획을 파악하기 위해 필요하고, "많아야 한 번"은 하드 드라이브가 중복으로 가득 차지 않게 하기 위해 필요하다.) Lisa가 Sarah에게 메시지를 애초에 보낼 수 없다면, 정부는 어떤 서버도 해킹하지 않는다.

이 조건을 만족하는 서버를 모두 구하자.

입력 파일의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 t가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스의 첫 줄에는 정수 n과 m이 주어진다. 다음 m개의 줄에는 각각 두 정수 a, b (1 ≤ a, b ≤ n)가 주어지며, 이는 서버 a가 서버 b로 메시지를 직접 전송할 수 있다는 뜻이다. (a = b일 수도 있다.) 서로 다른 순서쌍 a, b는 각각 최대 한 번만 주어진다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 줄에는 정부가 해킹할 수 있는 서버의 수를 출력한다. 둘째 줄에는 그 서버들의 번호를 공백으로 구분하여, Lisa가 Sarah에게 메시지를 보낼 때 메시지가 지나가는 순서대로 출력한다.

일부 테스트 케이스에서는 Lisa에서 Sarah로 가는 경로가 없을 수도 있다. 그런 경우에는 빈 서버 집합을 출력한다.