도청

동네 감시 협회가 우리 거리에 감시 시스템을 설치하려고 하고, 여러분이 이 일을 돕고 있다. 최근 잇따라 일어난 개똥 사건의 범인을 찾기 위해서다.

이 시스템은 거리의 깡통 전화선에 다는 도청 장치로 이루어진다. 개똥 범인들이 언젠가는 실수로 전화에서 자기들이 저지른 짓을 이야기하리라는 생각이다. 각 도청 장치는 두 집을 잇는 전화선 하나에 달며, 그 전화선을 지나는 통화를 모두 가로챈다.

전화선 네트워크는 다음과 같다. 거리 한쪽에는 홀수 번호 집이, 반대쪽에는 짝수 번호 집이 있다. 홀수 번호 집 $i$는 짝수 번호 집 $i + 1$의 바로 맞은편에 있다. 거리 양쪽 모두 이웃한 두 집 사이에 직통 전화선이 있다. 이와 별도로 거리를 가로지르는 직통 전화선이 두 개 있는데, 둘 다 어떤 집과 그 바로 맞은편 집을 잇는다.

같은 쪽에 있는 두 집 사이의 통화는 반대편으로 건너가지 않고 두 집 사이를 곧바로 잇는 경로로 전달된다. 서로 반대편에 있는 두 집 사이의 통화는 거리를 가로지르는 두 직통 전화선 중 어느 쪽을 쓰는지 알려져 있다. 또한 지난 경험으로 거리에서 누가 누구와 연락하고 지내는지도 알고 있다. 우리는 모든 통화를 가로챌 수 있게 도청 장치를 달고 싶다. 즉, 서로 연락하고 지내는 두 사람마다 두 사람의 집 사이 경로 위에 도청 장치가 있어야 한다.

도청 장치는 꽤 비싸고 지난주 바비큐 파티에 예산을 거의 다 써 버렸다. 이 조건을 만족하는 데 필요한 도청 장치의 최소 개수를 구하라.

그림 I.1: 예제 입력 1의 전화선 네트워크. 집은 모두 14채로 양쪽에 7채씩 있고, 거리를 가로지르는 두 직통 전화선은 3번 집과 4번 집, 9번 집과 10번 집을 잇는다. 7번 집과 11번 집 사람은 연락하고 지내며, 둘의 통화는 9번 집을 거친다. 5번 집과 6번 집 사람도 연락하고 지내며, 둘의 통화는 7번, 9번, 10번, 8번 집을 거친다. 예제 입력 2도 비슷하지만 5번 집과 6번 집 사이의 통화가 3번 집과 4번 집 사이의 직통 전화선을 거친다.

첫째 줄에 네 정수 $n$, $m$, $c_1$, $c_2$가 주어진다 ($4 \le n \le 250\,000$, $1 \le m \le 500\,000$, $1 \le c_1 < c_2 < n$). $n$은 짝수이고 거리에 있는 집의 수이다. $m$은 서로 연락하고 지내는 사람 쌍의 수이다. $c_1$과 $c_2$는 홀수이며, 거리를 가로지르는 두 전화선이 $c_1$번 집과 $c_1 + 1$번 집 사이, $c_2$번 집과 $c_2 + 1$번 집 사이를 잇는다는 뜻이다.

다음 $m$개의 줄은 각각 1 이상 $n$ 이하인 서로 다른 두 정수 $a$, $b$로 시작하며, $a$번 집 사람과 $b$번 집 사람이 연락하고 지낸다는 뜻이다. 두 집이 거리의 서로 반대편에 있으면 그 뒤에 정수 $c \in \{c_1, c_2\}$가 하나 더 주어진다. 이는 $a$와 $b$ 사이의 통화가 $c$번 집과 $c + 1$번 집 사이의 직통 전화선을 거친다는 뜻이다. 같은 쌍 $\{a, b\}$는 입력에 많아야 한 번 나온다.

필요한 도청 장치의 최소 개수 $l$을 한 줄에 출력한다.