#комбинаторика #задача

N олигархов построили себе страну c N городами, каждый олигарх владеет ровно одним городом. Кроме того, каждый олигарх построил несколько дорог между городами: любая пара городов соединена максимум одной дорогой каждого из олигархов (между двумя городами может быть несколько дорог, принадлежащих разным олигархам). Суммарно было построено d дорог. Некоторые олигархи хотели бы создать корпорацию, объединив свои города и дороги, так чтобы при этом из любого города корпорации можно было доехать до любого другого ее города по дорогам этой корпорации, возможно, заезжая по дороге в города других олигархов. Но оказалось, что никакая группа, в которой меньше N олигархов создать корпорацию не может! При каком наибольшем d это возможно?