32203번 - 연락

문제

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 \le i \le N)$
• 1ドル \leq a_{i}, b_{i} \leq N(1 \le i \le M)$
• $a_{i} \neq b_{i}(1 \le i \le M)$

힌트