인터넷 문제 (어려움)

Lisa와 Sarah는 부패한 정부의 음모를 폭로했고, 지금은 정부를 피해 도망 중이다. 둘이 함께 있으면 둘 다 붙잡힐 위험이 커서 인터넷으로 연락한다. 일반 인터넷은 충분히 안전하지 않아서, 다크 웹을 통해 비밀 메시지를 주고받는다.

다크 웹에서는 메시지가 여러 서버를 거치는 길고 복잡한 경로를 따라 목적지에 도달한다. 경로가 같은 서버를 여러 번 지나갈 수도 있어서 메시지 추적이 훨씬 어렵다.

그래도 Lisa는 걱정이 남아 있다. 정부가 이미 다크 웹의 서버 하나를 해킹했다면 어떻게 될까? 해킹된 서버가 좋은 중심 위치에 있다면, 메시지가 어떤 경로로 가든 Lisa가 Sarah에게 보내는 메시지를 모두 가로챌 수 있다.

Lisa의 인터넷 문제를 풀어 달라.

다크 웹은 $n$개의 서버로 이루어져 있으며, 서버에는 1부터 $n$까지 번호가 붙어 있다. 서버들은 $m$개의 방향 링크로 연결되어 있다. 한 서버가 다른 서버로 메시지를 보낼 수 있다고 해서 그 반대도 반드시 성립하지는 않는다. Lisa는 서버 1에, Sarah는 서버 $n$에 연결되어 있다. Lisa가 Sarah에게 메시지를 보낼 때마다 경로를 하나 고른다. 경로는 서버 1에서 서버 $n$까지 이어지는 연속된 링크의 열이다. 경로는 각 서버를 여러 번 지나도 된다.

정부는 Lisa가 Sarah에게 보내는 메시지를 가로채려 한다. 서버 하나를 해킹하면 그 서버를 지나는 모든 메시지를 기록할 수 있다. 정부는 Lisa에서 Sarah로 가는 모든 메시지를 정확히 한 번씩 보고 싶어 한다. 최소 한 번은 전체 계획을 알기 위해서 필요하고, 최대 한 번은 중복 메시지로 하드 디스크가 차지 않게 하기 위해서 필요하다.

이 조건을 만족하는 서버를 모두 찾아라.

첫 줄에 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다.

각 테스트 케이스의 첫 줄에는 정수 $n$과 $m$이 주어진다. 이어지는 $m$개의 줄에는 정수 $a$, $b$ ($1 \le a, b \le n$)가 한 쌍씩 주어지며, 이는 서버 $a$가 서버 $b$로 메시지를 직접 보낼 수 있다는 뜻이다. $a = b$인 경우도 있다. 같은 순서쌍 $a, b$는 두 번 이상 주어지지 않는다.

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

Lisa에서 Sarah로 가는 경로가 없는 테스트 케이스에서는 빈 집합을 출력한다.

$2 \le n \le 500000$

$0 \le m \le 1000000$

첫 번째 테스트 케이스: 모든 메시지가 같은 경로를 따르므로, 정부는 그 경로 위의 어느 서버든 해킹할 수 있다.

두 번째 테스트 케이스: 정부는 중복을 원하지 않으므로 두 서버 어느 것도 해킹할 수 없다. Lisa와 Sarah는 안전하다.

세 번째 테스트 케이스: Lisa는 어차피 메시지를 보낼 수 없으므로 해킹할 대상이 없다.

네 번째 테스트 케이스: 정부는 2번과 3번을 동시에 해킹할 수 없다. 2번만 또는 3번만 해킹하면 모든 메시지를 볼 수 없다.