Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Обход в глубину
    Компоненты сильной связности(3 задач)
    Мосты(2 задач)
    Применение обхода в глубину(3 задач)
    Топологическая сортировка(2 задач)
    Точки сочленения(1 задач)
---> 1 задач <---
Источники --> Командные олимпиады --> Командные чемпионаты школьников Санкт-Петербурга по программированию
    1999(5 задач)
    2000(7 задач)
    2001(8 задач)
    2002(8 задач)
    2003(9 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(10 задач)
    2008(9 задач)
    2009(10 задач)
    2010(10 задач)
    2011(9 задач)
    2012(10 задач)
    2013(10 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: 1 Отображать по:
#1760
Железные дороги
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes
В мультиграфе могут добавляться и удаляться ребра. После каждого добавления и удаления необходимо вывести длину максимального пути, такого, что все вершины на пути имеют степень 2 (кроме начальной и конечной)

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

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

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

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

Входные данные

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

Выходные данные

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

Примеры
Входные данные
7 10
0 7 6 7
0 6 5 6
0 5 4 5
0 4 3 4
0 3 2 3
0 2 1 2
1 1
1 2
1 3
1 4
Выходные данные
7
13
18
22
25
27
20
14
9
5
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест