Маємо орієнтований граф з \(N\) вершинами. Вершини пронумеруємо від 1 до \(N\). У момент часу 0 граф не має ребер. Для кожного \(t = 1, 2, \ldots, T\), у момент \(t\), будується ребро з вершини \(u_t\) до вершини \(v_t\). (може бути \(u_t = v_t\), якщо вершина не перша)

Вершина називається хорошою, якщо її можна досягти, починаючи з вершини 1 і проходячи через ребра рівно \(L\) разів.

Для кожного \(i = 1, 2, \ldots, N\) виведіть найменший час, коли вершина \(i\) стане хорошою.

Якщо немає часу, коли вершина \(i\) стане хорошою, то виведіть -1.

Формат вхідних даних

Перший рядок містить цілі числа \(N, T, L\) (\(2 \le N \le 100\), \(1 \le T \le N^2\), \(1 \le L \le 10^9\))

Наступні  \(T\) рядків містять цілі числа \(u_t, v_t\) (\(1 \le u_t, v_t \le N\), \(i \neq j⇒(u_i​,v_i​) \neq (u_j​,v_j​)\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть у такому форматі для кожного \(i = 1, 2, \ldots, N\) найменший час \(X_i\) коли вершина \(i\) стане хорошою. Якщо такого часу немає, то виведіть -1.

X_1​ X_2 ... X_N

Примітка

До прикладу 1:

У момент 0 граф не має ребер. Ребра додаються наступним чином.

• У момент 1 додається ребро від вершини 2 до вершини 3.

• У момент 2 додається ребро від вершини 3 до вершини 4.

• У момент 3 додається ребро від вершини 1 до вершини 2. Тепер вершина 4 може бути досягнута з вершини 1 рівно за трьома кроками: \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\), що робить вершину 4 хорошою.

• У момент 4 додається ребро від вершини 3 до вершини 2. Тепер вершина 2 може бути досяжна з вершини 1 рівно за три кроки: \(1 \rightarrow 2 \rightarrow 3 \rightarrow 2\), що робить вершину 2 хорошою.

• У момент 5 додається ребро від вершини 2 до вершини 2. Тепер вершина 3 може бути досяжна з вершини 1 рівно за трьома ходами: \(1 \rightarrow 2 \rightarrow 2 \rightarrow 3\), що робить вершину 3 хорошою.

Вершина 1 не буде хорошою.

Приклад вхідних даних

4 5 3
2 3
3 4
1 2
3 2
2 2

Приклад вихідних даних

-1 4 5 3

Приклад вхідних даних

2 1 1000000000
1 2

Приклад вихідних даних

-1 -1