8706번 - Wrogie Państwa 다국어

Bitocja i Bajtocja planują podpisać rozejm po długotrwałej wojnie. Państwa te muszą zdecydować, do kogo będą należeć poszczególne miasta. Władcy Bitocji i Bajtocji postanowili, że dokonają podziału tak, aby zminimalizować liczbę bezpośrednich połączeń między parami miast, należącymi do różnych państw.

Twoim zadaniem jest podanie wspomnianej wyżej liczby po podpisaniu rozejmu.

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n i m (1 ≤ n ≤ 500, 0 ≤ m ≤ n(n - 1)/2), oznaczające odpowiednio liczbę miast oraz liczbę połączeń. Drugi wiersz wejścia zawiera ciąg liczb całkowitych a₁, a₂, ..., a_n (1 ≤ a_i ≤ 3). Jeżeli a_i ma wartość 1, to miasto i należeć będzie do Bitocji, 2, to miasto i należeć będzie do Bajtocji, 3, to miasto i należy przydzielić albo do Bajtocji albo do Bitocji. Kolejnych m wierszy zawiera opisy połączeń między miastami. Każdy wiersz opisu zawierać będzie dwie liczby a, b, (1 ≤ a < b ≤ n) oznaczające, że miasta a i b są połączone bezpośrednią drogą. Żadna para (a, b) się nie powtórzy.

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie połączeń między miastami należącymi do Bitocji i Bajtocji po podpisaniu rozejmu.

Jeżeli miasto numer 3 zostanie przydzielone Bitocji, to występować będzie tylko jedno połączenie między miastami Bitocji i Bajtocji - między miastami 3 i 4.