Infinite Stamps via Teleporters

The pharaohs have discovered n planets numbered from \(0\) to \(n-1\) and established a one-way teleporter network between them. In this network, each teleporter is a directed edge from a start planet to a destination planet. Note that the start planet and destination planet may be the same. We represent a teleporter from planet \(u\) to planet \(v\) as \((u, v)\).

To encourage the use of this system, the pharaohs designed a game for travelers. A traveler may begin his journey from any planet. Planets \(0,1,\dots, k-1\) (where \(k \le n\)) are called special planets. Every time a traveler enters a special planet, he receives a stamp.

Initially, for each planet \(i\) (\(0 \le i \le k-2\)), a teleporter \((i, i+1)\) is built. These \(k-1\) teleporters are known as the initial teleporters.

Then new teleporters are added over time. A traveler might be able to earn infinitely many stamps if there exists a sequence of planets \(w[0], w[1], \dots, w[t]\) satisfying:

• \(t \ge 1\).
• \(0 \le w[0] \le k-1\) (i.e. the sequence starts from a special planet).
• \(w[t] = w[0]\) (i.e. the sequence forms a cycle).
• For each \(i\) (\(0 \le i \le t-1\)), a teleporter \((w[i], w[i+1])\) exists.

Note that the traveler may choose to use any teleporter available, including the initial teleporters and any that have been added so far.

Your task is to help the pharaohs verify, after each new teleporter is added, whether a traveler can collect infinitely many stamps.

Function Specifications

void init(int n, int k)

• n: The total 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 starting and destination planets of the teleporter to be added.
• This function will be called at most \(m\) times.
• If after adding teleporter \((u,v)\) a traveler is able to obtain infinitely many stamps, return \(1\); otherwise, return \(0\).
• Once the function returns \(1\), your program will be terminated.

Input / Output (for offline simulation)

To simulate the interactive environment, you will write an offline program that reads from standard input. The first line contains three integers: \(n\), \(k\), and \(m\). The next \(m\) lines each contain two integers \(u\) and \(v\) representing a new teleporter added via add_teleporter.

Initially, the system already has the teleporters \((0,1)\), \((1,2)\), \(\dots\), \((k-2, k-1)\). Process the \(m\) queries sequentially. For each query, output the return value (either \(0\) or \(1\)). Once a query returns \(1\), terminate the processing (i.e. do not handle further queries).

Note

A cycle is valid only if it starts (and eventually returns) to one of the special planets. The cycle may use any of the already available teleporters.

inputFormat

The first line contains three space-separated integers \(n\), \(k\), and \(m\) representing the number of planets, the number of special planets, and the number of teleporter additions respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\) (\(0 \le u,v < n\)) representing the teleporter that is being added.

outputFormat

For each teleporter addition, output a single integer per line. If after adding the teleporter a traveler can obtain infinitely many stamps, output \(1\) and terminate the program immediately. Otherwise, output \(0\).

sample

5 3 3
2 0
0 4
4 2

1

</p>