Задача 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