Exact Distance Paths

The traffic system of city \(W\) consists of \(n\) stations and \(m\) directed roads. Xiaowei holds a one-ride ticket that allows him to travel exactly \(k\) kilometers. At each station, he can choose any available outgoing road. Each road represents a distance of 1 kilometer (or one station transition).

Your task is to determine all pairs of stations \((u, v)\) such that there exists a path from station \(u\) to station \(v\) with exactly \(k\) edges. Output the pairs in lexicographical order (i.e. sorted first by the starting station and then by the ending station).

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\), representing the number of stations, the number of directed roads, and the required path length in kilometers, respectively. Each of the following \(m\) lines contains two integers \(u\) and \(v\), indicating a directed road from station \(u\) to station \(v\).

outputFormat

For every station \(u\) from which there exists a path of exactly \(k\) kilometers to some station \(v\), output a line containing the pair u v. The pairs should be printed in lexicographical order: first by \(u\) in ascending order, and then by \(v\) in ascending order.

sample

3 3 2
1 2
2 3
1 3

1 3