## JOI '14 - Space Pirate

View as PDF

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

Problem type
Allowed languages
C, C++, Sed, Text
##### Contest Day 1 - JOI Open Contest

Long long ago, in a galaxy far, far away..., there are highly civilized stars numbered from to . Each star provides one teleporter. Each teleporter has a fixed destination. We travel through a teleporter only in one direction.

The Galactic Empire Museum of Art holds art exhibitions in stars in the galaxy. Now the exhibition is held in the star . The next exhibition will be held in the star where we travel from the star using the teleporters times.

The Space Police found that a space pirate is planning to steal collections of the museum. The space pirate will crack into the teleporter system, and illegally overwrite the destination of the teleporter in the star . The destination of the teleporter in the star will be modified to the star . The space pirate will crack into the teleporter system of one star only. However, the Space Police could not find the precise values of , .

In order to predict the location of the next exhibition, the Space Police would like to know, for each , the number of pairs such that the next exhibition will be held in the star . To calculate these numbers is a difficult job. Since you are a good programmer, the Space Police asked you to calculate them.

Given the destination of each teleporter, for each , calculate the number of pairs such that the next exhibition will be held in the star .

#### Input

Read the following data from the standard input.

• The first line of input contains two space separated integers and . This means there are stars in the galaxy, and the next exhibition will be held in the star where we travel from the star 1 using the teleporters times.
• The line () of the following lines contains an integer (). This means the current destination of the teleporter in the star is the star .

#### Output

Write lines to the standard output. The line () should contain an integer, the number of pairs such that the next exhibition will be held in the star .

#### Note

• The destination of the teleporter in the star may be the star itself. In this case, we will stay in the star if we travel from the star using the teleporter many times.
• Even if the current destination of the teleporter in the star is the star , the space pirate may crack into the teleporter system and overwrite the destination to be the star . In this case, the destination of the teleporter in the star will still be the star ; it will not be changed. Such pairs should be included when you count the number of pairs satisfying the conditions in the task statement.

#### Constraints

All input data satisfy the following conditions:

• .
• .

• .

• .

• ().

#### Sample Input 1

5 7
5
1
4
3
2

#### Sample Output 1

1
2
3
3
16

#### Explanation for Sample 1

The destination of each teleporter is described in Figure 1.

If , the destination of the teleporter in the star 1 will be overwritten to the star 4. The destination of each teleporter will become as in Figure 2. We will arrive at the star 4 if we travel from the star 1 using the teleporters times. Therefore, the next exhibition will be held in the star 4. (We travel as 1 → 4 → 3 → 4 → 3 → 4 → 3 → 4 using the teleporters.)

There are three pairs of (i.e. , , ) where the next exhibition will be held in the star 4. The location of the next exhibition for each pair is summarized in the following table.

The pair such that the next exhibition will be held in the star .
,
, ,
, ,
, , , , , , , , , , , , , , ,

When you count the number of pairs , the pairs with should be counted. You should also count the pairs such that the destination of the teleporter will not be changed.

#### Sample Input 2

40 57
9
24
1
28
29
5
9
1
36
5
35
14
14
29
28
34
28
4
34
36
33
11
22
23
10
18
26
33
36
15
37
31
27
16
25
37
6
31
21
31

#### Sample Output 2

4
2
1
12
18
9
1
1
15
0
4
0
0
2
0
11
0
12
0
2
0
0
1
0
5
12
13
13
34
0
5
1
15
10
8
1351
36
1
0
1