графы

Алиса и Боб играют в очень интересную карточную игру. На каждой карте в этой игре написано одно целое число. На протяжении игры у Боба в каждой из двух рук находится ровно одна карта. Изначально Боб держит в левой руке карту с числом 0, а в правой руке — также карту с числом 0.

Алиса делает \(n\) ходов. На ходу с номером \(i\) она предлагает Бобу карту с числом \(k_i\), а также 4 числа \(a_i\), \(b_i\), \(c_i\), \(d_i\). Боб выбирает, в какую руку он хочет взять новую карту, после чего выбрасывает карту из этой руки и берет в эту руку новую карту Алисы. После этого Алиса проверяет карты Боба. А именно, пусть он в левой руке держит карту \(x\), а в правой — карту \(y\). Тогда должно выполняться \(a_i \le x \le b_i\) и \(c_i \le y \le d_i\), иначе игра немедленно заканчивается.

Боб заранее знает все числа \(k_i\), \(a_i\), \(b_i\), \(c_i\) и \(d_i\). Помогите ему выбрать для каждого хода, в левую или правую руку ему следует класть очередную карту, чтобы в итоге все условия Алисы были выполнены.

В первой строке вводятся два целых числа \(n\) и \(m\) (\(2 \le n \le 100\,000\), \(2 \le m \le 10^9\)) — количество ходов в игре и максимально возможное число, записанное на карте.

Далее следует описание \(n\) ходов. Каждое описание состоит из трех строк.

Формат входных данных
В первой строке описания \(i\)-го запроса вводится целое число \(k_i\) (\(0 \le k_i \le m\)) — число, записанное на новой карте.

Во второй строке описания \(i\)-го запроса вводятся два целых числа \(a_i\) и \(b_i\) (\(0 \le a_i \le b_i \le m\)) — минимальное и максимальное допустимые значения для карты из левой руки после хода \(i\).

В третьей строке описания \(i\)-го запроса вводятся два целых числа \(c_i\) и \(d_i\) (\(0 \le c_i \le d_i \le m\)) — минимальное и максимальное допустимые значения для карты из правой руки после хода \(i\).

Формат выходных данных
Если Боб не сможет удовлетворить все условия Алисы, выведите <<No>>. Иначе в первой строке выведите <<Yes>>, а затем в следующей строке выведите \(n\) чисел — в какую руку Бобу следует класть очередную карту: если Бобу нужно взять карту в левую руку, выведите 0, иначе выведите 1. В случае, если у Боба существует несколько способов удовлетворить условиям Алисы, выведите любой из них.

В первом примере из условия Боб может взять карту из первого хода в левую руку. После этого у него в руках будут карты \(3\) и \(0\), которые соответствуют ограничениям (\(0 \le 3 \le 3\) для левой руки и \(0 \le 0 \le 2\) для правой).

Карту из второго хода Боб может взять в правую руку, после чего в его руках будут карты \(3\) и \(2\), которые соответствуют ограничениям (\(0 \le 3 \le 4\) для левой руки и \(0 \le 2 \le 2\) для правой руки). Таким образом, Боб может удовлетворить всем ограничениям Алисы, и в этом случае ответ <<Yes>>.

IT-компания <<VK>> имеет огромную инфраструктуру проектов, и чтобы разработчики могли гармонично работать вместе и структурировать вносимые в код изменения, им необходима система контроля версий (VCS).

Полноценные системы контроля версий устроены достаточно сложно, и некоторые компании даже разрабатывают свои собственные VCS, заточенные под конкретные нужды или особенности рабочего процесса. Разумеется, разработчики из <<VK>> могут справиться с задачей реализовать свою VCS, но сегодня эта задача предлагается вам.

Ваша примитивная система контроля версий должна иметь вид дерева изменений состояния проекта.

• Корень дерева — стартовая вершина, соответствующая изначальному состоянию проекта. Это единственная вершина, в которую не входят ребра.

• Каждая вершина, кроме корня, соответствует определенному коммиту. Коммит — блок из одного или более изменений.

• Версия проекта, задаваемая вершиной — набор всех изменений на путях между стартовой вершиной и данной.

• Есть несколько выделенных веток, каждая имеет уникальное имя и задается указателем на определенную вершину дерева. С веткой ассоциируется версия проекта, соответствующая вершине, на которую она указывает.

• Из всех веток выделяется текущая ветка — версия проекта, с которой сейчас работает пользователь. Вершину, на которую указывает текущая ветка, будем обозначать как HEAD.

Пример дерева можно видеть ниже. Рядом с каждым коммитом указаны соответствующие ему изменения. Вершины номер \(8\) и \(9\) появляются после команды rebase между ветками <<main>> и <<new_config>> (описание команд см. ниже). Набор команд, позволяющий получить приведенную структуру графа версий, приведен в первом тесте. Пошаговые иллюстрации изменения графа версий можно видеть в прикрепленном к условию архиве.

Изначально дерево состоит из единственной вершины с номером \(1\), на которую указывает текущая ветка <<main>>. Требуется поддерживать следующие команды:

1. <<add <файл> <хеш изменений>>> — запомнить изменения, внесенные в данный файл. Хеш однозначно описывает набор изменений в файле. Иными словами, хеши двух независимых изменений совпадают тогда и только тогда, когда в файл были внесены одинаковые изменения.

   Иными словами, если в пустой файл добавляется строчка <<print(something)>>, и в непустой файл добавляется та же строчка, хеши этих двух изменений будут различными.

2. <<commit>> — подвесить к HEAD новую вершину, состоящую из всех изменений (add), сделанных с момента предыдущего успешного коммита. Новой вершине присваивается первый неиспользованный натуральный номер, после чего HEAD перемещается на нее.

   Операция возможна только тогда, когда множество сделанных изменений непустое. В противном случае требуется выдать ошибку <<FAILURE: no changes>>, при этом новая вершина не создается.

3. <<reset <номер>>> — переместить HEAD на вершину с данным номером.

   Гарантируется, что вершина с данным номером существует. Если присутствуют несохраненные (commit) изменения (add), операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>.

4. <<checkout <имя ветки>>> — поменять текущую ветку на ветку с указанным именем (и, соответственно, переместить HEAD на версию, соответствующую выбранной ветке). Если ветки с таким именем не существует, создать новую ветку с таким именем, которая будет указывать на HEAD, после чего сделать ее текущей.

   Если присутствуют несохраненные изменения, операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>, аналолгично операции reset.

5. <<rebase <имя ветки>>> — перенести изменения из ветки с указанным именем в текущую ветку. При этом находится ближайший общий предок двух веток и все коммиты в укзанной ветке после общего предка (то есть все вершины, которых нет в текущей ветке) копируются и вставляются в текущую ветку после HEAD в исходном порядке. HEAD при этом перемещается на последнюю из скопированных вершин, а указатель второй ветки не двигается. Гарантируется, что имя второй ветки не совпадает с текущей.

   Если есть незакоммиченные изменения, операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>.

   Если несохраненных изменений нет, проверяется отсутствие конфликтов при объединении. Конфликтом считается ситуация, когда в состояниях проекта, соответствующим данным веткам, с одним и тем же файлом сделаны различные изменения. Иными словами, если обозначить множество изменений определенного файла в текущей ветке как \(D_1\), а во второй — как \(D_2\), то конфликт возникает, когда оба множества \(D_1 \setminus D_2\) и \(D_2 \setminus D_1\) непустые. В таком случае операция отклоняется с ошибкой <<FAILURE: conflicts detected>>.

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

   Если какое-то изменение содержится в версиях разное ненулевое количество раз (например, изменение может присутствовать дважды после rebase двух веток, в которые оно входило), конфликт не возникает. Конфликт возникает только если в каждой версии есть измененение одного и того же файла, которого нет в другой версии.

   Ниже можно найти иллюстрации к успешным и конфликтным вызовам операции rebase.

   

   

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово <<SUCCESS>> и номер вершины, на которую указывает HEAD, если команда выполнена успешно, или же соответствующую ошибку, если команда отклонена.

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных, которые вам предстоит обработать (\(1 \le T \le 20\)). Далее следуют описания наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное целое число \(n\) — количество команд в наборе (\(0 \le n \le 400\)). В \(i\)-й из следующих \(n\) строк задается \(i\)-я команда.

Гарантируется, что имена веток состоят только из маленьких латинских букв (‘a’ – ‘z’) и нижних подчеркиваний (‘_’), а хеши изменений — уникальные шестнадцатеричные строки длины ровно \(6\) (состоят из цифр и маленьких латинских букв от ‘a’ до ‘f’). Имена файлов в команде add состоят из маленьких латинских букв, точек и слешей (‘/’).

Также гарантируется, что команде reset всегда передается существующая вершина, а команде merge — существующая ветка, не совпадающая с текущей.

Формат выходных данных
Для каждого набора входных данных в порядке их следования во вводе сначала выведите строку <<Test case <номер>>> (наборы нумеруются от \(1\) до \(T\)), а затем \(n\) результатов выполнения команд, каждый в своей строке.

Результат выполнения каждой команды должен соответствовать либо формату <<SUCCESS <HEAD>>>, либо формату <<FAILURE: <сообщение об ошибке>>>.

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

У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ. 
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.

Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).

Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.

Тесты разделены пустой строкой для читабельности.

Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 5 4 1 2 2 3 1 4 3 5	3	G′ может быть равен G′ или одному из двух следующих графов: 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5
2	7 4 6 1 2 2 3 3 4 1 3 2 4 1 4 5 5 1 2 2 3 3 4 4 5 1 5 5 7 1 2 1 3 1 5 2 4 3 3 3 4 4 5 6 6 1 2 2 3 3 4 4 5 5 6 6 6 6 7 1 2 2 3 1 3 1 4 4 5 5 6 1 6 10 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 22 28 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 8 3 9 8 10 10 11 10 12 10 13 10 14 11 15 12 16 13 17 14 18 9 15 9 16 9 17 9 18 15 19 19 20 15 20 16 21 21 22 16 22	45 35 11 1 15 371842544 256838540	Это пример более крупного теста. Обязательно выводите ответ по модулю \(10^9+7\). Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\).