What is an EJOI for you?
Game room!
Teo is searching for the Croatian EJOI team! She has already found Gabriel, but is still looking for Vito, Dino, and Ivo.
Teo and the EJOI team are in a labyrinth consisting of P
), red (marked with C
), green (marked with Z
) and
orange (marked with N
).
Illustration of the third example. The black circle marks the room in which Teo and Gabriel are located in the fourth question, and the white circle marks the room in which Vito, Ivo and Dino are located. The gray path is one of the possible paths that passes through three different door colors.
At some point, Gabriel says:
I know where the rest of the team is, but I will only tell you if you can answer all of my questions.
Gabriel's questions are:
If we are currently in room
and the rest of the team is in room , what is the minimum number of door colors we have to go through to reach them?
Teo is very good at answering Gabriel's questions, but there are simply too many of them. She does not
have much time (the bus is leaving soon), so she is asking you to help her answer
Input Specification
The first line contains integers
The P
, C
, Z
or N
), where the
The P
, C
, Z
or N
), where the
The next line contains the integer
In the
Output Specification
In the
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 11 | |
2 | 13 | All doors that connect rooms |
3 | 24 | Every door is either red or blue. |
4 | 22 | No additional constraints. |
Sample Input 1
1 8
CPZNCCP
4
1 1 1 8
1 3 1 5
1 8 1 4
1 2 1 3
Sample Output 1
4
2
3
1
Sample Input 2
3 3
PP
PP
PP
CCC
CCC
3
1 1 3 3
3 3 2 2
1 1 1 3
Sample Output 2
2
2
1
Sample Input 3
4 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 1
Sample Output 3
1
2
1
3
Explanation for Sample 3
The third example is illustrated in the problem statement.
For the first question, Teo and Gabriel can use just the blue doors to reach the rest of the team; for the second question, they can use blue and green doors; for the third, again, only blue is enough; and for the fourth, they can use blue, green, and red doors.
Comments