(Задача от Джордано)

Ваша фабрика имеет N соединений (пронумерованных от 1 до N), соединенных M конвейерными лентами. Каждая конвейерная лента автоматически транспортирует любой продукт из одного перекрестка в другой ровно за одну минуту. Обратите внимание, что каждая конвейерная лента работает только в одном направлении. Может быть более одной конвейерной ленты, соединяющей два соединения, и может быть конвейерная лента, соединяющая соединение с самим собой. Есть K производителей (машины, которые производят продукты), расположенные на первых K соединениях, то есть на соединениях 1, 2,. , , , K. Производитель в соединении j производит продукт каждую минуту (x · K + j) для всех целых чисел x ≥ 0 и j = 1, 2,. , , , K. Все продукты немедленно транспортируются через конвейерные ленты на склад в месте соединения N, за исключением тех, которые произведены в месте соединения N (если есть). Товары, произведенные на стыке N, доставляются непосредственно на склад (нет необходимости использовать конвейерные ленты). На каждом перекрестке робот решает, к каким ленточным конвейерам должен поступить поступающий продукт за незначительное время (мгновенно). Роботы могут быть запрограммированы таким образом, чтобы все товары, произведенные производителем, всегда доставлялись на склад по одному и тому же маршруту. После того, как роботы запрограммированы, маршрут больше не может быть изменен. Товары от разных производителей могут иметь одинаковые или разные маршруты. Приходит осмотрительный потенциальный инвестор, который хочет осмотреть фабрику, прежде чем принимать какое-либо решение. Вы хотите показать потенциальному инвестору, что на вашем предприятии действует хорошая политика управления рисками. Таким образом, вы хотите убедиться, что каждая конвейерная лента транспортирует не более одного продукта одновременно; два продукта не могут быть на одной и той же конвейерной ленте одновременно. С другой стороны, количество продуктов на стыках не ограничено. Чтобы достичь этого, вы можете отключить ноль или более производителей, но вы все равно хотите максимизировать производство. Определите максимальное количество производителей, которое можно оставить работающим так, чтобы все произведенные продукты могли быть доставлены на склад, и каждая конвейерная лента перевозит не более 1 продукта в любое время.

в первой строке 3 числа N, K, M (N <= 300, K <= N, M <= 1000)
далее идет M строк, описывающая соединения (u, v)

Ограничения: 4 секунды и 64мб на тест