Поиск самых длинных цепочек совпадающих устройств

Набор A имеет n устройств. В наборе B есть m устройств. Некоторые устройства в A совместимы с устройствами в B, а некоторые устройства в B совместимы с устройствами в A.

Я хочу, чтобы как можно больше совместимых устройств было подключено друг к другу. (Не обязательно, чтобы устройство a в A и b в B было взаимно совместимым.)

Отредактируйте для ясности : любое устройство может быть связано с 0, 1 или 2 другими устройствами, но не с самим собой.

В конце концов, все устройства (или все, кроме двух, если «концы» не совпадают) должны быть связаны друг с другом 1 на 1. Можно связать одно устройство с любым другим устройством. Но ни одно устройство в A не совместимо с каким-либо устройством в A (но они связываемые ), и то же самое верно для устройств в B.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

Тогда граф G

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

является оптимальным графом.

G не обязательно должен быть циклическим, но может быть.

Есть ли какие-нибудь умные способы подойти к этому?