28333번 - 화이트 칼라

문제

전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다.

오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 검거하기 위한 작전을 세우고 있다. AdbyMe, Inc. 는 그가 현재 어느 도시에 있는지, 그리고 뮤직박스가 어느 도시에 있는지 파악했고, 그를 잡기 위해 직원들을 배치할 것이다. AdbyMe, Inc. 가 입수한 정보에 의하면 닐 카프리는 매우 급한 성격 (?)이고, 그의 성격으로 볼 때, 현재 위치에서 뮤직박스가 있는 곳까지 최단 경로로 이동할 것이다.

그래서 AdbyMe, Inc. 는 현재 닐 카프리가 있는 도시와 뮤직박스가 있는 도시, 그리고 그가 이동할 때 거쳐갈 가능성이 있는 모든 도시에 직원들을 배치하려고 한다. 지도를 보고 직원들을 배치해야 되는 도시를 모두 골라내자.

입력

입력은 $T$개의 테스트 케이스로 구성된다. 입력의 첫 행에는 $T$가 주어진다.

각 테스트 케이스의 첫 행에는 도시의 수 $N$ (2ドル ≤ N ≤ 1,000円$), 도시 간에 연결된 길의 수 $M$ (1ドル ≤ M ≤ 50,000円$)이 주어진다. 그 다음 $M$행에 연결된 도시의 번호 $A_i$와 $B_i$가 주어진다. 모든 길은 그 길이가 같은 $A_i$에서 $B_i$로 이동하는 일방통행 길이다. (1ドル ≤ A_i , B_i ≤ N,ドル $A_i \ne B_i$)

닐 카프리는 현재 1ドル$번 도시에 위치해 있고, 뮤직박스는 $N$번 도시에 위치해 있다. 1ドル$번 도시에서 $N$번 도시로 이동 가능한 경로는 반드시 하나 이상 존재한다.

출력

각 테스트 케이스에 대해 한 행에 하나씩 AdbyMe, Inc. 가 직원들을 배치해야하는 도시의 번호를 오름차순으로 출력한다.

제한

힌트