Wrogie Państwa
Limit pamięci: 64 MB
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.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite i (), oznaczające
odpowiednio liczbę miast oraz liczbę połączeń.
Drugi wiersz wejścia zawiera ciąg liczb całkowitych ().
Jeżeli ma wartość 1, to miasto należeć będzie do Bitocji, 2, to miasto należeć będzie do Bajtocji,
3, to miasto należy przydzielić albo do Bajtocji albo do Bitocji.
Kolejnych wierszy zawiera opisy połączeń między miastami.
Każdy wiersz opisu zawierać będzie dwie liczby , , () oznaczające, że
miasta i są połączone bezpośrednią drogą. Żadna para (, ) się nie powtórzy.
Możesz założyć, że w testach wartych około punktów zachodzi dodatkowy warunek
Wyjście
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.
Przykład
Dla danych wejściowych:
4 4
1 1 3 2
1 2
1 3
2 3
3 4
poprawną odpowiedzią jest:
1
Wyjaśnienie do przykładu: 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.
Autor zadania: Joanna Bujnowska (zapożyczenie).