Задача ACCESS. Готовясь к олимпиаде по ИКТ знатоки баз данных (а знатоки есть, ведь все изучают ACCESS!) столкнулись с такой задачей: есть база, которая задает ориентированный граф в виде таблицы вершин, между которыми есть ребро. Нужно сделать запросы 2-х видов:
- добавить новое ребро в граф;
- сообщить количество ребер в кратчайшем пути от первой вершины до заданной.
Или ACCESS «не очень СУБД» для работы с базами, или «знатоки НЕ знатоки», но не получилось ... Знатоки ИКТ просят вас, программистов, написать программу, которая будет выполнять указанные запросы по мере их поступления: сообщать кратчайшее расстояние от первой вершины к заданной и добавлять новые ребра. Понятно, что перед началом работы программы база пуста. А вот ответы на запросы почему-то пользователю надо получать в обратном порядке.
Технические условия. Программа ACCESS читает с устройства стандартного ввода в первой строке два числа N, М (1 ≤ N ≤ 1000, 1 ≤ M ≤ 30 000) – количество вершин и количество запросов.
В кожной из следующих M строк содержится информация о запросе в базу:
- "+ x y"- добавить ребро в граф, которое идет из вершины x к вершине y (1 ≤ x, y ≤ N);
- "? k" – определить кратчайший путь из первой вершины (то есть с номером 1) к вершине с номером k (то есть минимальное количество ребер, входящих в такой путь).
Программа выводит через пробелы в одну строку на устройство стандартного вывода ответ на запросы о длине кратчайшего пути в порядке, обратном их поступления. Если пути из первой вершины к указанной не существует, выведите -1.
Пример
Ввод
2 4
? 2
+ 1 2
? 1
? 2
Вывод
1 0 -1