eolymp
bolt
Try our new interface for solving problems
Məsələlər

Домино

Домино

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до M включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3). Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны. Некоторые костяшки были удалены из полного набора. Требуется определить, какое минимальное количество цепочек нужно выложить из оставшихся в наборе костяшек, чтобы каждая из них принадлежала ровно одной цепочке.

Напишите программу, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.

Giriş verilənləri

В первой строке содержится одно целое число M (0 M 100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число N, равное количеству костяшек, удаленных из полного набора. Каждая i-я из последующих N строк содержит по два числа A_i и B_i. Это количества точек на половинках i-й удалённой костяшки.

Çıxış verilənləri

Вывести одно целое число L - минимальное количество цепочек.

Nümunə

Giriş verilənləri #1
7
2
7 5
3 4
Çıxış verilənləri #1
2
Müəllif Andrey Stasyuk
Mənbə 2005 XVIII All-Ukrainian Informatics Olympiad, Rovno, April 10 - 16, Round 2