Super Pipeline Transportation

In a distant galaxy, the fastest mode of transportation is the super pipeline. Each super pipeline connects \(K\) stations together. There are a total of \(N\) stations and \(M\) super pipelines. Each super pipeline is described by a list of \(K\) station numbers that it connects. Using these pipelines, you can instantly travel between any two stations that belong to the same pipeline.

Your task is to determine the minimum number of stations you must pass through (including the starting station \(1\) and the destination station \(N\)) to travel from station \(1\) to station \(N\). If it is not possible to reach station \(N\), output \(-1\).

Note: The formulas use LaTeX format. For example, the number of stations per pipeline is given as \(K\), and the starting and ending stations are \(1\) and \(N\), respectively.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\) separated by spaces, where \(N\) is the number of stations, \(M\) is the number of super pipelines, and \(K\) is the number of stations in each super pipeline.

This is followed by \(M\) lines. Each of these lines contains \(K\) integers, representing the station numbers that are connected by that super pipeline.

outputFormat

Output a single integer: the minimum number of stations required to travel from station \(1\) to station \(N\). If station \(N\) is unreachable, output \(-1\).

sample

9 3 3
1 2 3
3 4 5
5 8 9

4