У вас есть \(n\) дисков, радиус \(i\)-го диска равен \(i\). Изначально эти диски распределены по \(m\) башням из дисков: каждая башня содержит хотя бы один диск, и диски в каждой башне отсортированы от большего к меньшему снизу вверх.
Вы должны собрать все диски в одну башню. Чтобы сделать это, вы можете выбрать две различных башни \(i\) и \(j\) (каждая из которых содержит хотя бы один диск), взять несколько (возможно, все) верхних дисков с башни \(i\) и поместить их на вершину башни \(j\) в том же самом порядке — при условии, что верхний диск башни \(j\) больше каждого перемещаемого диска. Эту операцию можно применять любое количество раз.
Например, если у вас есть две башни, содержащие диски \([6, 4, 2, 1]\) и \([8, 7, 5, 3]\) (в порядке снизу вверх), существуют ровно две возможные операции:
- переместить диск \(1\) с первой башни на вторую, после чего башни станут следующими: \([6, 4, 2]\) и \([8, 7, 5, 3, 1]\);
- переместить диски \([2, 1]\) с первой башни на вторую, после чего башни станут следующими: \([6, 4]\) и \([8, 7, 5, 3, 2, 1]\).
Пусть сложность некоторого набора башен — это минимальное количество операций, необходимых для того, чтобы собрать все диски в одну башню. Например, сложность набора башен \([[3, 1], [2]]\) равна \(2\): вы можете переместить диск \(1\) на вторую башню, а потом переместить оба диска со второй башни на первую башню.
Вам заданы \(m - 1\) запросов. Каждый запрос обозначается двумя числами \(a_i\) и \(b_i\), обозначающими следующее: «слить башни \(a_i\) и \(b_i\) в одну» (то есть взять все диски из этих башен и составить из них одну башню, в которой диски отсортированы по убыванию размера снизу вверх). Новая башня (являющаяся результатом слияния) получает индекс \(a_i\).
Для каждого \(k \in [0, m - 1]\) посчитайте сложность набора башен после выполнения первых \(k\) запросов.