Hämähäkit haluavat ylittää rotkon käyttäen rakentamaansa verkkoa. Hämähäkkien verkko muodostuu solmuista ja niitä yhdistävistä linkeistä. Verkko on kuitenkin niin hauras, että aina kun hämähäkki lähtee eteenpäin solmusta, solmu tuhoutuu eikä toinen hämähäkki voi käyttää sitä.

Tehtäväsi on selvittää, montako hämähäkkiä voi ylittää rotkon.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua n, m ja w: solmujen määrä, linkkien määrä ja rotkon leveys. Solmut on numeroitu 1,2,\ldots,n.

Tämän jälkeen syötteessä on n riviä, jotka kuvaavat solmut. Jokaisella rivillä on kaksi kokonaislukua x ja y: solmun koordinaatit.

Solmut, joiden x-koordinaatti on 0, ovat rotkon vasemmalla reunalla, ja solmut, joiden x-koordinaatti on w, ovat rotkon oikealla reunalla. Aluksi kaikki hämähäkit ovat vasemmalla reunalla ja he haluavat päästä oikealle reunalle.

Lopuksi syötteessä on m riviä, jotka kuvaavat linkit. Jokaisella rivillä on kokonaisluvut a ja b, mikä tarkoittaa, että solmujen a ja b välissä on linkki. Kaikki linkit ovat kaksisuuntaisia. Lisäksi mitkään linkit eivät leikkaa toisiaan, joten verkko on tasoverkko.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako hämähäkkiä voi ylittää rotkon.

Esimerkki

Syöte:

7 8 4
0 1
0 2
0 3
2 2
2 3
4 1
4 3
1 4
2 4
3 4
3 5
4 5
5 7
5 6
4 6

Tuloste:

2

Rajat

• 1 \le w \le 10^9
• 0 \le x \le w
• 0 \le y \le 10^9
• 1 \le a,b \le n

Osatehtävä 1 (20 pistettä)

• 1 \le n \le 10
• 1 \le m \le 20

Osatehtävä 2 (30 pistettä)

• 1 \le n \le 100
• 1 \le m \le 200

Osatehtävä 3 (50 pistettä)

• 1 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5