Вы разрабатываете программу для майнинга блоков в новом блокчейне. В данный момент вам нужно релизовать модуль для выбора транзакций, включенных в блок.

На вход данному модулю подается набор из $n$ \textit{транзакций}, пронумерованных от $1$ до $n$. Транзакции исполняются в специальной виртуальной машине. Память данной машины состоит из $m$ \textit{локаций}, пронумерованных от $1$ до $m$. Для каждой локации вам заранее известно множество локаций памяти, из которых данная транзакция производит чтения, и множество локаций памяти, в которые она производит запись. Для $i$-й транзакции обозначим эти множества как $RS_i$ и $WS_i$.

Из данного множества транзакций модуль должен выбрать некоторое подмножество и упорядочить его. Пусть модуль выбрал $k$ транзакций с номерами $p_1, p_2, \ldots, p_k$. Для возможности спекулятивного исполнения, в выбранной последовательности транзакций не должно быть \textit{конфликтов}. Конфликтом называется пара транзакций, где та транзакция, которая идет раньше, записывает в некоторую локацию памяти, откуда потом читает другая транзакция. Более формально, транзакции $p_i$ и $p_j$ где $i < j$ конфликтуют, если существует такая локация памяти $l$, что $l \in WS_{p_i}$ и $l \in RS_{p_j}$.

По данному множеству транзакций вам нужно выбрать из него последовательность транзакций наибольшей возможной длины, не содержащей конфликтов. Вам не требуется находить оптимальное решение в данной задаче. Ваше решение получит количество баллов, пропорциональное длине найденной вами последовательности транзакций.