Вам задано дерево, состоящее из \(n\) вершин (пронумерованных от \(1\) до \(n\)) и \(n-1\) ребер (пронумерованных от \(1\) до \(n-1\)). Изначально все вершины, кроме вершины \(1\), неактивны.
Вам предстоит обрабатывать запросы трех типов:
- \(1\) \(v\) — активировать вершину \(v\). Гарантируется, что вершина \(v\) неактивна перед этим запросом, а один из ее соседей активен. После активации вершины выберите подмножество ребер дерева таким образом, чтобы каждая активная вершина была инцидентна ровно одному выбранному ребру, и каждая неактивная вершина не была инцидентна ни одному из выбранных ребер — другими словами, это подмножество должно является совершенным паросочетанием активной части дерева. Если такое подмножество ребер существует, выведите сумму индексов ребер в нем; в противном случае выведите \(0\).
- \(2\) — запросы этого типа будут задаваться только сразу после запроса типа \(1\), и таких запросов будет не более \(10\). Если ваш ответ на предыдущий запрос был \(0\), просто выведите \(0\); в противном случае выведите подмножество ребер для предыдущего запроса в следующем формате: сначала выведите количество ребер в подмножестве, затем выведите индексы выбранных ребер в порядке возрастания. Сумма индексов должна быть равна вашему ответу на предыдущий запрос.
- \(3\) — завершить программу.
Обратите внимание, что вы должны решить эту задачу в режиме online. Это означает, что вы не можете считать все входные данные сразу. Вы можете считать каждый запрос только после вывода ответа на предыдущий запрос. Используйте функции fflush в C++ и BufferedWriter.flush в Java после каждого вывода в вашей программе.
Выходные данные
Для каждого запроса типа \(1\) или \(2\) выведите ответ в отдельной строке в формате, описанном в условии. Не забывайте сбрасывать буфер вывода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 4
6 1
3 2
1 2
5 1
1 4
2
1 2
2
1 3
2
1 5
1 6
2
3
|
1
1 1
0
0
4
2 1 3
0
0
0
|