필수 경유 정점

정점이 $N$개이고 간선이 $M$개인 방향 그래프와 시작 정점 $S$가 주어진다. 정점의 번호는 $0$부터 $N-1$까지이다. 자기 루프와 중복 간선이 있을 수 있다.

$S$에서 도달할 수 있는 정점 $v$에 대해, $S$에서 $v$로 가는 모든 경로가 지나는 정점을 $v$의 필수 경유 정점이라고 한다. 경로의 시작점과 끝점도 포함한다.

$v \ne S$이면 $v$ 자신을 제외한 필수 경유 정점 중 $v$에 가장 가까운 정점을 구해 보자. 이는 $S$에서 $v$로 가는 각 경로에서 $v$ 자신을 제외하고 마지막으로 지나는 필수 경유 정점이며, 항상 하나로 정해진다. $S$의 답은 $S$, 도달할 수 없는 정점의 답은 $-1$이다.

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 200)$

각 테스트 케이스의 첫 번째 줄에 세 정수 $N$, $M$, $S$가 공백으로 구분되어 주어진다. $(1 \le N \le 10\,000; 0 \le M \le 100\,000; 0 \le S < N)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 시작 정점 번호 $u$, 끝 정점 번호 $v$가 공백으로 구분되어 주어진다. $(0 \le u, v < N)$

전체 테스트 케이스에서 $N$의 합은 $30\,000$ 이하이고 $M$의 합은 $200\,000$ 이하이다.

각 테스트 케이스마다 $0$번부터 $N-1$번 정점까지의 답을 공백으로 구분하여 한 줄에 출력한다.