Ən uzun yol

Verilmiş istiqamətli qrafda elə bir ən uzun yolu tapın ki, qrafın hər bir zirvəsi bu yolda yalnız bir dəfə istifadə olunsun.

Giriş məlumatları

Birinci sətirdə iki tam ədəd n və m (1 ≤ n ≤ 22, 0 ≤ m ≤ 1000) verilir. Sonrakı m sətirdə qrafın kənarları u[i] v[i] formatında verilir - burada i-ci kənarın başlanğıc və son zirvələrinin nömrələri göstərilir. Qraf döngələr və çoxlu kənarlar ehtiva edə bilər.

Çıxış məlumatları

Birinci sətirdə tapılmış yolun uzunluğunu l çıxarın. İkinci sətirdə isə l + 1 ədəd - yolun keçid sırasına uyğun zirvələri çıxarın. Əgər bir neçə optimal cavab varsa, onlardan istənilən birini çıxarmaq olar.

Nümunələr