Лето 6

В некоторой стране есть развитая сеть железных дорог. С доисторических времён и до нашего времени в стране непрерывно происходят военные перевороты, из-за которых в системе железнодорожного транспорта этой страны происходят непрерывные изменения. Дело в том, что во время очередного переворота некоторые дороги разрушаются из-за военных действий, а пока новый правитель некоторое время находится у власти, он восстанавливает часть дорог.

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

Инженер Джио проводит испытания новых сверхскоростных поездов. Поскольку поезда экспериментальные, у них не должно возникать трудностей при проезде через промежуточные города. Поэтому инженер Джио требует, чтобы ни в каком городе на пути поезда, кроме, может быть, начального и конечного, не было развилок. Точнее, из любого промежуточного города на пути поезда должны выходить либо ровно две дороги, ведущие в другие города (возможно, в один и тот же), либо ровно одна дорога, начинающаяся и заканчивающаяся в этом городе.

Естественно, что Джио желает испытать поезд на максимальной возможной скорости, и поэтому после каждого изменения в системе путей он хочет знать максимальную длину пути, по которому может ехать поезд. Поскольку в доисторические времена не умели добывать железо, в начале никаких дорог между городами нет.

В первой строке входного файла находятся целые положительные числа `n` (`1≤\ n≤500`) — число городов в стране, и `m` (`1≤\ m≤50\ 000`) — число изменений в железнодорожной системе. В следующих `m` строках находится информация об изменениях состояния системы путей. Каждое изменение является либо добавлением дороги, либо удалением дороги. В случае добавления дороги в очередной строке записан ноль, а затем идут три целых числа. Первые два из них являются номерами городов, соединяемых дорогой, а последнее является длиной добавленной дороги. Города нумеруются целыми числам от 1 до `n`. Длина дороги является целым положительным числом, не превосходящим `10^6`. В случае удаления дороги в очередной строке сначала записана единица, а затем идёт номер шага, на котором произошло добавление удаляемой дороги. Шаги нумеруются целыми числами, начиная с 1.

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

5 16
0 2 3 4
0 3 4 3
0 1 2 1
0 5 5 4
1 1
1 4
0 4 1 4
0 4 5 1
0 1 4 1
1 7
0 1 5 7
1 2
1 3
1 8
1 9
1 11

4
7
8
*
*
3
8
5
4
3
8
9
*
8
7
0