hackercupai/hackercup huggingface dataset:
**Note: The only difference between this and [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-3/problems/D2/) is that here, you only need to find the answer for a single \(K\).**

Boss Rob ain’t Som Tawyer, but he can paint a fence alright.

Rob's fence is made of \(N\) wooden stakes, numbered \(1\) to \(N\) from left to right. Initially (at time \(0\)), the \(i\)th stake is of color \(i\). There is a fencepost before stake \(1\) and after stake \(N\), as well as after every \(K\)th stake starting from the left.

Rob has a simple and joyful plan to repaint his fence, consisting of \(M\) moments in time. At time \(i\), he'll repaint all stakes which are color \(A_i\) to color \(B_i\). Doing so, when would be the *first time* that all pairs of stakes not separated by a fencepost have the same color? If it will never occur, consider the answer to be \(-1\).

# Constraints

\(1 \le T \le 40\)
\(1 \le N, M \le 600{,}000\)
\(1 \le K \le N\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)

The sum of \(N\) across all test cases is at most \(4{,}000{,}000\).
The sum of \(M\) across all test cases is at most \(4{,}000{,}000\).

# Input Format

Input begins with an integer \(T\), the number of test cases. For the \(i\)th test case, there is first a line containing three space-separated integers \(N\), \(M\), and \(K\). Then, \(M\) lines follow, the \(i\)th of which contains two space-separated integers \(A_i\) and \(B_i\).

# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the first time that the condition is satisfied, or \(-1\) if will never be.

# Sample Explanation

The progressions of fences for the first two sample cases are depicted below:

{{PHOTO_ID:1207042806525380|WIDTH:700}}

In the first case, all stakes between fenceposts will have the same color after time \(2\).

In the second case, all stakes between fenceposts will have the same color after time \(3\).

In the third case, the fence progresses as follows:

{{PHOTO_ID:1173386423530703|WIDTH:700}}

At no point in time will all stakes between pairs of fenceposts have the same color.