Задача ACCESS. Готовясь к олимпиаде по ИКТ знатоки баз данных (а знатоки есть, ведь все изучают ACCESS!) столкнулись с такой задачей: есть база, которая задает ориентированный граф в виде таблицы вершин, между которыми есть ребро. Нужно сделать запросы 2-х видов:

- добавить новое ребро в граф;

- сообщить количество ребер в кратчайшем пути от первой вершины до заданной.

Или ACCESS «не очень СУБД» для работы с базами, или «знатоки НЕ знатоки», но не получилось ... Знатоки ИКТ просят вас, программистов, написать программу, которая будет выполнять указанные запросы по мере их поступления: сообщать кратчайшее расстояние от первой вершины к заданной и добавлять новые ребра. Понятно, что перед началом работы программы база пуста. А вот ответы на запросы почему-то пользователю надо получать в обратном порядке.

 Технические условия. Программа ACCESS читает с устройства стандартного ввода в первой строке два числа N, М (1 ≤ N ≤ 1000, 1 ≤ M ≤ 30 000) – количество вершин и количество запросов.

В кожной из следующих M строк содержится информация о запросе в базу:

  1. "+ x y"- добавить ребро в граф, которое идет из вершины x к вершине y (1 ≤ x, y ≤ N);
  2. "? k" – определить кратчайший путь из первой вершины (то есть с номером 1) к вершине с номером k (то есть минимальное количество ребер, входящих в такой путь).

Программа выводит через пробелы в одну строку на устройство стандартного вывода ответ на запросы о длине кратчайшего пути в порядке, обратном их поступления. Если пути из первой вершины к указанной не существует, выведите -1.

Пример

Ввод  

2  4
? 2

+ 1 2
? 1
? 2

Вывод     

1 0 -1

© LIKT 1998-2018