Background

This problem only supports C++ submissions. When submitting, you do not need to include the game.h header file; you only need to paste the contents of game.h from the attachment at the beginning of your code.

Problem Description

The Pharaohs discovered $n$ planets numbered from $0$ to $n - 1$, and built a one-way teleportation system between them. In this system, each teleporter connects a start planet and a destination planet. When a tourist uses a teleporter from its start planet, they will arrive at the corresponding destination planet. Note that the start planet and the destination planet may be the same planet. We use $(u, v)$ to denote a teleporter that starts at planet $u$ and ends at planet $v$.

To promote the widespread use of the teleportation system, the Pharaohs designed a game for tourists to play while traveling. A tourist may start from any planet. Planets numbered $0, 1, \dots, k - 1$ ($k \le n$) are called special planets. Each time the tourist enters a special planet, they obtain one stamp.

Currently, for each planet $i$ ($0 \le i \le k - 2$), a teleporter $(i, i + 1)$ has been built. These $k - 1$ teleporters are called initial teleporters.

Teleporters are continuously built over time. As teleporters are added, it may become possible for a tourist to obtain infinitely many stamps. More precisely, this happens when there exists a planet sequence $w[0], w[1],\dots , w[t]$ satisfying:

• $1 \le t$.
• $0 \le w[0] \le k - 1$.
• $w[t] = w[0]$.
• For each $i$ ($0 \le i \le t - 1$), there exists a teleporter $(w[i], w[i + 1])$.

Note that a tourist can use both the initial teleporters and any teleporter that has already been built.

Your task is to help the Pharaohs check, after each new teleporter is added, whether a tourist can obtain infinitely many stamps.

Implementation Details

You need to implement the following functions:

init(int n, int k)

• $n$: the number of planets.
• $k$: the number of special planets.
• This function is called exactly once, before any call to add_teleporter.

int add_teleporter(int u, int v)

• $u$ and $v$: the start and destination planets of the teleporter being added.
• This function is called at most $m$ times (see the “Constraints” section for the range of $m$).
• If after adding teleporter $(u, v)$ it is possible for the tourist to obtain infinitely many stamps, the function must return $1$. Otherwise, it should return $0$.
• Once the function returns $1$, your program will be terminated.

Input Format

The sample grader reads the input in the following format:

• Line $1$: $n\ m\ k$.
• Line $2 + i$ ($0 \le i \le m - 1$): $u[i]\ v[i]$.

The sample grader first calls init, and then calls add_teleporter in the order $i = 0, 1,\dots , m - 1$ with $u = u[i]$ and $v = v[i]$.

Output Format

The program needs to print the index (from $0$ to $m - 1$, inclusive) of the first call to add_teleporter that returns $1$. If all calls to add_teleporter return $0$, your program should output $m$.

If some call to add_teleporter returns an integer other than $0$ or $1$, the sample grader will print $-1$, and your program will be terminated immediately.

6 5 3
3 4
5 0
4 5
5 3
1 4

4

4 1 2
1 1

0

4 3 2
1 3
2 0
3 2

2

Hint

Constraints

• $1\le n\le 3\times 10^5$；
• $1\le m\le 5\times 10^5$；
• $1\le k\le n$。

For each call to the add_teleporter function:

• $0\le u\le n-1$ and $0\le v\le n-1$；
• Before teleporter $(u,v)$ is added, there is no teleporter from planet $u$ to planet $v$.

Subtasks

1. ($2$ points) $n=k$, $n\le 100$, $m\le 300$；
2. ($10$ points) $n\le 100$, $m\le 300$.
3. ($18$ points) $n\le 10^3$, $m\le 5\times 10^3$。
4. ($30$ points) $n\le 3\times 10^4$, $m\le 5\times 10^4$, $k\le 10^3$。
5. ($40$ points) No additional constraints.

Examples

Example $1$

Consider the following function call:

init(6, 3)

In this example, there are $6$ planets and $3$ special planets. Planets numbered $0, 1, 2$ are special planets. The initial teleporters are $(0, 1)$ and $(1, 2)$.

Suppose the grader performs the following calls:

• (0) add_teleporter(3, 4): should return $0$.
• (1) add_teleporter(5, 0): should return $0$.
• (2) add_teleporter(4, 5): should return $0$.
• (3) add_teleporter(5, 3): should return $0$.
• (4) add_teleporter(1, 4): in this case, it is possible to obtain infinitely many stamps. For example, the tourist can start from planet $0$ and travel in the order $1, 4, 5, 0, 1, 4, 5, 0,\dots$. Therefore, the function should return $1$, and then your program will be terminated.

The figure below illustrates this example. Special planets and initial teleporters are shown in bold. Teleporters added via add_teleporter are labeled from $0$ to $4$ in the order they are added.

Example $2$

Consider the following function call:

init(4, 2)

In this example, there are $4$ planets and $2$ special planets. Planets numbered $0$ and $1$ are special planets. The initial teleporter is $(0, 1)$.

Suppose the grader performs the following call:

• add_teleporter(1, 1): after adding teleporter $(1, 1)$, we can obtain infinitely many stamps. For example, a tourist can start from planet $1$ and use teleporter $(1, 1)$ to reach planet $1$ infinitely many times. Therefore, the function should return $1$, and then your program will be terminated.

The attachment package also includes another sample input and output.

Translated by ChatGPT 5