Interception

You are helping your local Neighborhood Surveillance Association set up a surveillance system on your street in order to identify the culprits behind some recent unfortunate dog doo incidents.

The system consists of listening devices placed on the tin-can phone lines of the street (the idea being that sooner or later the dog doo malefactors will slip up and discuss their dirty deeds over the phone). Each listening device is placed on one of the phone lines connecting the houses, and it intercepts all calls that are routed along that phone line.

The phone line network looks as follows. One side of the street has odd-numbered houses, and the other side has even-numbered houses. The numbers are lined up so that odd-numbered house $i$ is directly across the street from even-numbered house $i + 1$. On both sides of the street, there are direct phone lines between adjacent pairs of houses. In addition, there are two direct phone lines connecting the two sides of the street. Each of these two phone lines connects a house with the house directly across from it.

Calls between two houses on the same side of the street are routed along the direct path between the two houses, without going to the other side of the street. For calls between two houses on opposite sides of the street, we know which of the two direct connections across the street the call uses. From previous ventures, we also know which people on the street are on speaking terms with each other. We would like to place listening devices so that we can intercept all phone calls. In other words, for every pair of people that are on speaking terms with each other, there must be a listening device on the route between their houses.

Listening devices are fairly expensive, and we burnt most of our budget on the barbecue last week. Your job is to find the minimum possible number of listening devices needed to do this.

Figure I.1: The phone line network in Sample Input 1. There are 14 houses, 7 on each side, and the two direct connections across the street connect house 3 with house 4, and house 9 with house 10. The people in houses 7 and 11 are on speaking terms, and calls between them are routed via house 9. The people in houses 5 and 6 are also on speaking terms, and calls between them are routed via houses 7, 9, 10, and 8. Sample Input 2 is similar, but there the calls between 5 and 6 are instead routed via the direct connection between houses 3 and 4.

The first line of input contains four integers $n$, $m$, $c_1$, and $c_2$ ($4 \le n \le 250\,000$, $1 \le m \le 500\,000$, $1 \le c_1 < c_2 < n$). Here $n$ is even and is the number of houses on the street, $m$ is the number of pairs of people that are on speaking terms with each other, and $c_1$ and $c_2$ are odd, meaning that the two wires crossing the street go between houses $c_1$ and $c_1 + 1$, and between houses $c_2$ and $c_2 + 1$.

Then follow $m$ lines, each beginning with two distinct integers $a$ and $b$ between 1 and $n$ (inclusive), indicating that the person in house $a$ is on speaking terms with the person in house $b$. If the two houses are on opposite sides of the street, they are followed by an integer $c \in \{c_1, c_2\}$ indicating that calls between $a$ and $b$ are routed along the direct connection between houses $c$ and $c + 1$. Each pair $\{a, b\}$ appears at most once in the input.

Output one line with an integer $l$, the smallest possible number of listening devices needed.