Задача J. Сборка генома SARS-CoV2 ≡

Условие

Даны N нуклеотидных последовательностей ридов длиной L, полученных с участков генома коронавируса SARS-CoV2. Требуется написать программу, создающую граф де Брюйна, проверяющую наличие эйлерова пути и строящую по этому пути искомую нуклеотидную последовательность (геном). Кратными ребрами (мультиграф) пренебрегаем, то есть считаем за одно, если направление ребер одинаковое. Между альтернативными ребрами выбирается лексиграфически наименьшее. Длина вершины/узла графа должна быть равна 30 нуклеотидам, а ребро — 31. Количество вершин в графе обычно не более количества ридов.

Формат входного файла

Входной файл имеет формат FASTA и содержит L ридов.

Формат выходных данных

Выходной файл должен содержать одну нуклеотидную последовательность (геном), если есть эйлеров путь по графу, иначе None

Ограничения

N < 4000

L ≤ 100.

Примеры тестов

>simulated.1
CACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTGATGAAGGTAATT
>simulated.2
ATGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGA
>simulated.3
ATATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTAT
>simulated.4
ATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTATGC
>simulated.5
TGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGAC
>simulated.6
GACATGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGC
>simulated.7
TCTTACTAAATACACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTG
>simulated.8
TACTAAATACACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTGATG
>simulated.9
GTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCT
>simulated.10
ATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTATGCTT

GACATGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTGATGAAGGTAATT