У Владислава есть плейлист, состоящий из \(n\) песен, пронумерованных от \(1\) до \(n\). Песня \(i\) имеет жанр \(g_i\) и автора \(w_i\). Он хочет составить плейлист таким образом, чтобы каждая пара соседних песен либо имела одного и того же автора, либо была из того же жанра (или и то, и другое). Он называет такой плейлист захватывающим. И \(g_i\), и \(w_i\) являются строками, длины не более \(10^4\).
Не всегда возможно составить захватывающий плейлист, используя все песни, поэтому процесс перемешивания происходит в два этапа. Сначала удаляются некоторое количество (возможно, нулевое) песен, а затем оставшиеся песни в плейлисте переставляются, чтобы сделать его захватывающим.
Поскольку Владислав не любит, когда песни удаляются из его плейлиста, он хочет, чтобы составление плейлиста выполнялось с минимальным количеством удалений. Помогите ему найти минимальное количество удалений, которые необходимо выполнить, чтобы можно было переставить оставшиеся песни, чтобы сделать плейлист захватывающим.
Выходные данные
Для каждого теста выведите одно целое число — минимальное количество удалений, необходимых для того, чтобы получившийся плейлист можно было сделать захватывающим.
Примечание
В первом тесте плейлист уже захватывающий.
Во втором тесте, если у вас есть песни в порядке \(4, 3, 1, 2\), это захватывающий плейлист, поэтому вам не нужно удалять никакие песни.
В третьем тесте вы можете удалить песни \(4, 5, 6, 7\). Тогда плейлист с песнями в порядке \(1, 2, 3\) будет захватывающим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
pop taylorswift
4
electronic themotans
electronic carlasdreams
pop themotans
pop irinarimes
7
rap eminem
rap drdre
rap kanyewest
pop taylorswift
indierock arcticmonkeys
indierock arcticmonkeys
punkrock theoffspring
4
a b
c d
e f
g h
|
0
0
4
3
|