Збирання гірлянди

Вася на Новий рік купив ялинкову гірлянду "Зроби сам".

У її комплект входять:

• 2 \cdot N різнокольорових лампочок, серед них немає лампочок однакового кольору;

• 2 \cdot N патронів, у які ці лампочки потрібно вкрутити;

• достатня кількість провідників, щоб під'єднати патрони з вкрученими у них лампочками до мережі.

Кожен патрон має деяку кількість контактів для під'єднання провідників. У комплекті представлено $N$ типів патронів. Патрон першого типу має один контакт для під'єднання провідника, у патрона другого типу таких контактів два, у патрона третього типу ― три контакти для провідників, і т.д. Патрони типу $N$ мають $N$ контактів для під'єднання провідників. Патронів кожного типу є рівно по дві штуки.

Гірлянда запрацює, якщо так розподілити лампочки між патронами і з'єднати відповідні патрони провідниками, щоб виконувались такі умови:

• в усіх патронах усі контакти для провідників повинні бути використані;

• до одного контакту патрона повинен бути під'єднаним лише один провідник;

• у будь-якого провідника обидва кінці повинні бути під'єднані до контактів двох різних патронів;

• не можна два різних патрона з'єднувати більше ніж одним провідником.

Для Васі ця задача здалась дуже важкою. Допоможіть йому зібрати гірлянду до Нового року.