ЛОШ-2016: Задачечки на строчечки

Мэр столицы Котоляндии, наконец, согласился построить в городе метро. Теперь его ожидает чрезвычайно важная задача — сэкономить как можно больше денег на его постройке.

Метро будет состоять из определенного количества станций, соединенных двусторонними тоннелями. Между каждой парой станций должен быть путь по тоннелям (возможно, через другие станции), при этом количество построенных тоннелей должно быть минимально возможным. Заметьте, что при таких условиях существует единственный путь между каждой парой станций.

Пассажиры должны будут заплатить некоторое количество денег для того, чтобы войти в метро на определенной станции. При этом для разных станций эта сумма может быть разной. А именно: для некоторой станции x стоимость входа (в гривнах) будет равна максимальному количеству тоннелей, которые пассажир должен проехать для того, чтобы доехать от станции x к любой другой станции y .

Кроме того, мэр города очень придирчив к числам. Известно, что мэр любит числа a ₁ , ..., a _n , а также ненавидит числа b ₁ , ..., b _m . Мэр не согласится на постройку метро, если в стоимости прохода в метро хотя бы на одной из станций будет хотя бы одно число, которое он ненавидит, а также если не будет ни одной станции с стоимостью прохода, равной какому-то числу, которое он любит.

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