## APIO '22 P2 - Game

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
C++

After discovering planets, numbered from to , the Pharaohs have started to build a transportation system between them by one-way teleporters. Each teleporter has a starting planet and an ending planet. When a tourist uses a teleporter in the starting planet, the tourist is teleported to the ending planet. Note that the starting and ending planet of a teleporter may be the same. A teleporter with its starting planet and ending planet is denoted by .

To encourage widespread use of the teleportation system, the Pharaohs have created a game that can be played by tourists while travelling with the transportation system. A tourist can start the game from any planet. The planets () are called special planets. Every time a tourist enters a special planet, the tourist gets a stamp.

Currently, for each (), there is a teleporter . These teleporters are called starting teleporters.

New teleporters are added one by one. As new teleporters are added, it may become possible for a tourist to get an infinite number of stamps. To be precise, this happens when there is a sequence of planets satisfying the following conditions:

• For each (), there is a teleporter .

Note that a tourist can use starting teleporters and any teleporters that have been added so far.

Your task is to help the Pharaohs verify, after the addition of each teleporter, whether a tourist can get an infinite number of stamps or not.

#### Implementation Details

You should implement the following procedures:

void init(int n, int k)

• : the number of planets.
• : the number of special planets.
• This procedure is called exactly once, before any calls to add_teleporter.
int add_teleporter(int u, int v)

• and : the starting and the ending planet of the added teleporter.
• This function is called at most times (for the value of , see Constraints).
• This function should return if, after the teleporter is added, the tourist can get infinite number of stamps. Otherwise, this function should return .
• Once this function returns , your program will be terminated.

#### Examples

##### Example 1

Consider the following call:

init(6, 3)


In this example, there are planets and special planets. The planets , , and are special planets. The starting teleporters are and .

1. add_teleporter(3, 4): You should return .
2. add_teleporter(5, 0): You should return .
3. add_teleporter(4, 5): You should return .
4. add_teleporter(5, 3): You should return .
5. add_teleporter(1, 4): At this point, it is possible to get an infinite number of stamps. For example, the tourist starts in the planet , goes to the planets in this order. Hence, you should return , and your program will be terminated.

The following figure illustrates this example. The special planets and the starting teleporters are shown in bold. Teleporters added by add_teleporter are labeled from through , in order.

##### Example 2

Consider the following call:

init(4, 2)


In this example, there are planets and special planets. The planets and are special planets. The starting teleporter is .

1. add_teleporter(1, 1): after adding the teleporter , it is possible to get an infinite number of stamps. For example, the tourist starts in the planet , and enters the planet infinitely many times using the teleporter . Hence, you should return , and your program will be terminated.

Another sample input / output is available in the attachment package.

#### Constraints

For each call to the add_teleporter procedure:

• and
• There is no teleporter from the planet to the planet before adding the teleporter .

#### Scoring

, ,
,
,
, ,

• line :
• line ():

The sample grader first calls init, and then add_teleporter for and for in order.

It prints the index of the first call to add_teleporter which returns (which is between and , inclusive), or if all calls to add_teleporter return .

If some call to add_teleporter returns an integer other than or , the sample grader prints and your program is terminated immediately.