엘크

당신은 숲속에 있다. 이 숲에는 엘크 한 쌍도 있는데, 암컷(성체 암컷)과 그 새끼(어린 개체)이다. 대부분의 사람이 알다시피 암컷과 새끼 사이에 있는 것은 위험하지만, 이를 어떻게 피해야 하는지가 항상 명확한 것은 아니다.

숲은 $N$개의 장소와 이 장소들 사이의 $M$개의 직접 연결로 이루어져 있다고 모델링한다. 이 연결들은 어느 방향으로든 이동할 수 있다. 장소에는 $0$부터 $N-1$까지 번호가 매겨져 있고, 연결에는 $0$부터 $M-1$까지 번호가 매겨져 있다.

암컷에서 새끼까지의 경로를 다음 조건을 만족하는 일련의 장소 $p_0, p_1, p_2, \ldots , p_k$로 정의한다.

• $p_0$은 암컷이 있는 장소이다.

• $p_k$은 새끼가 있는 장소이다.

• $0 \le i < k$을 만족하는 각 $i$에 대해, 장소 $p_i$과 $p_{i+1}$ 사이에 직접 연결이 있다.

• 3번 조건의 연결 중 어느 것도 경로 내에서 반복되지 않는다. 단, 경로 내에서 장소가 반복되는 것은 허용한다.

명백히 이러한 경로 중 어느 하나에라도 포함되는 모든 장소는 위험한 곳이다. 암컷이 당신을 자신과 새끼 사이에 있다고 여길 수 있기 때문이다. 당신의 과제는 안전한 모든 장소, 즉 이러한 어떤 경로에도 포함되지 않는 장소를 찾는 것이다.

제약 조건

$2 \le N \le 5 \cdot 10^4$

$2 \le M \le 10^5$

모든 $i$에 대해 $0 \le U_i, V_i < N$.

$0 \leq A,B \leq N-1$

모든 $i$에 대해 $U_i \neq V_i$.

어떤 장소 쌍 사이에도 직접 연결은 최대 하나만 존재한다.

암컷에서 새끼까지의 경로는 항상 적어도 하나 존재한다.

채점

제출한 풀이는 각각 일정한 점수가 배정된 테스트 그룹들의 집합으로 평가된다. 각 테스트 그룹은 테스트 케이스들의 집합을 포함한다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 배점 | 제약 조건

$1$ |$10$| $N \le 10$, $M \le 45$

$2$ |$20$| $M = N-1$이고 그래프는 연결되어 있다.

$3$ |$30$| $N \le 200$, $M \le 500$

$4$ |$40$| 추가 제약 조건이 없다.

첫째 줄에 네 정수 $N, M, A, B$가 주어진다. $N$와 $M$은 각각 장소와 직접 연결의 개수이고, $A$과 $B$은 각각 암컷과 새끼가 현재 있는 장소이다.

이어지는 $M$개의 줄에는 $M$개의 연결 중 하나씩이 설명되며, 이 줄들에는 $0$부터 $M-1$까지 번호가 매겨져 있다. 이 중 $i$번째 줄에는 두 정수 $U_i$와 $V_i$가 주어지며, 이는 $i$번째 연결이 장소 $U_i$과 $V_i$ 사이의 연결임을 나타낸다.

출력의 첫째 줄에 숲에서 안전하게 있을 수 있는 장소의 개수인 정수 $S$ 하나를 출력한다.

이어지는 $S$개의 줄에 안전한 모든 장소를 한 줄에 하나씩 번호의 오름차순으로 출력한다.