연락

$1$번부터 $N$번까지 $N$명의 사람들은 친목을 다지기 위해 주기적으로 모임을 연다. $i$번 사람의 주민등록번호 뒷자리 첫 번째 숫자는 $c_i$이다. $c_i$가 $1, 3, 5, 7, 9$ 중 하나이면 남성이고, $0, 2, 4, 6, 8$ 중 하나이면 여성이다.

한 번의 모임에서 두 사람이 서로 전화번호를 교환한다. $i$번째 모임에서 전화번호를 교환하는 사람은 $a_i$번 사람과 $b_i$번 사람이다.

전화번호를 교환한 두 사람은 서로 연락 가능하다. 또한 임의의 $a$, $b$, $c$에 대해 $a$번 사람과 $b$번 사람이 연락 가능하고, $b$번 사람과 $c$번 사람이 연락 가능하면 $a$번 사람과 $c$번 사람도 연락 가능하다.

모임은 총 $M$번 진행되었다. $i = 1, 2, \cdots, M$에 대하여, $i$번째 모임이 끝난 직후 서로 연락 가능한 남녀 쌍의 개수의 최솟값을 구하라.

첫째 줄에 모임에 참석하는 사람의 수 $N$과 개최된 모임의 수 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 정수 $c_1, c_2, \cdots, c_N$이 공백으로 구분되어 주어진다. $c_i$는 $i$번 사람의 주민등록번호 뒷자리 첫 번째 숫자이다.

셋째 줄부터 $M$개의 줄에 걸쳐 $M$개의 모임에 관한 정보가 주어진다. $2 + i$번째 줄에는 $i$번째 모임에서 전화번호를 교환하는 $a_i$와 $b_i$가 공백으로 구분되어 주어진다.

첫 번째 줄부터 $M$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 모임 시점에서 서로 연락 가능한 남녀 쌍의 개수의 최솟값을 출력한다.

• $2 \leq N \leq 100\,000$
• $1 \leq M \leq 200\,000$
• $0 \leq c_i \leq 9$ ($1 \leq i \leq N$)
• $1 \leq a_i, b_i \leq N$ ($1 \leq i \leq M$)
• $a_i \neq b_i$ ($1 \leq i \leq M$)