잃어버린 섬 여행

당신은 공룡이 살아 숨쉬는, $N$개의 섬으로 이루어진 섬나라를 여행하게 되었다. 각 섬은 $1$번부터 $N$번까지 번호가 매겨져 있으며, 당신은 이 모든 섬을 빠짐없이 방문하려고 한다.

섬들 중 어떤 $M$개의 쌍에는 선후 관계가 존재한다. 섬 $a$에서 섬 $b$로 선후 관계가 존재한다면 반드시 $a$번 섬을 먼저 방문한 뒤에 섬 $b$를 방문해야 한다.

각 섬에는 $0$, $1$로 표시되는 두 종류 중 하나의 자외선 위험이 있다. 자외선으로부터 몸을 보호하기 위해 당신은 방호복을 입어야 한다. 같은 종류의 자외선 위험이 있는 섬을 연속으로 방문하는 경우에는 방호복을 갈아 입을 필요가 없지만, 한 종류의 자외선 위험이 있는 섬을 방문한 직후에 다른 종류의 자외선 위험이 있는 섬을 방문하려면 방호복을 갈아 입어야 한다.

처음 방호복을 입을 때에는 비용이 들지 않지만, 갈아입을 때마다 $1$의 비용이 든다.

모든 섬을 방문하는 데 드는 최소 비용을 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 섬의 개수를 나타내는 정수 $N$과 선후 관계의 개수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 200\,000;$ $0 \le M \le 400\,000$)

그다음 줄에 각 섬의 자외선 위험 종류가 섬 번호 순서대로 공백으로 구분되어 주어진다. 자외선 위험 종류는 $0$ 또는 $1$로 표현된다.

그다음 $M$개의 줄에 섬들의 선후 관계들이 섬 번호의 쌍으로 주어진다. 각 줄에는 두 정수 $a$, $b$가 공백으로 구분되어 주어지며, 이는 $a$번 섬을 먼저 방문한 다음 $b$번 섬으로 갈 수 있음을 뜻한다. ($1 \le a, b \le N;$ $a \ne b$)

같은 선후 관계는 두 번 이상 주어지지 않으며, 항상 주어진 선후 관계를 모두 만족하면서 모든 섬을 여행하는 것이 가능한 입력만 주어진다.

출력 형식

첫 줄에 모든 섬을 여행하기 위한 최소 비용을 출력한다.

예제 1

5 4
0 0 1 1 0
3 2
2 4
2 5
4 1

3

예제 2

4 0
1 1 1 1

0

예제 설명

섬 번호로 표현했을 때 $3$, $2$, $4$, $1$, $5$의 순서로 방문하면 방호복을 세 번 갈아입게 되며, 이 경우가 최선이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설