## QCC P1 - Quarantine Games

View as PDF

Points: 10
Time limit: 1.5s
Memory limit: 256M

Author:
Problem types

Quarantine can be very boring. To help pass the time, you've decided to watch piddddgy and deruikong play a game. The game is played on a directed acyclic graph with nodes numbered from to and edges each coloured red, orange, yellow, green, blue, indigo, or violet. To start the game, a token is placed on node , then piddddgy and deruikong take alternating turns with piddddgy starting first. A move consists of a player selecting the token and moving it along an edge to an adjacent node. The game ends when the token has visited all the colours on the graph, or it is impossible to make a move. The winner is then the last player who moved the token.

Assuming both piddddgy and deruikong play optimally, who is the winner of the game?

#### Input Specification

The first line of input will contain two space-separated integers, and .

The next lines that follow will each contain two integers, and , followed by a single character . This describes that there is a directed edge from to with colour .

#### Output Specification

Output the winner of the game, either piddddgy or deruikong.

#### Constraints

It is not guaranteed that all edges are distinct.

#### Sample Input 1

4 4
1 2 r
1 2 b
2 3 r
3 4 r

#### Sample Output 1

piddddgy

#### Explanation for Sample 1

The optimal game is played as follows:

Turn : piddddgy moves the token on the red edge from to .

Turn : deruikong moves the token on the red edge from to .

Turn : piddddgy moves the token on the red edge from to .

The game ends with piddddgy making the last move.

#### Sample Input 2

4 4
1 2 b
1 2 b
2 3 r
3 4 r

#### Sample Output 2

deruikong

#### Explanation for Sample 2

The optimal game is played as follows:

Turn : piddddgy moves the token on the blue edge from to .

Turn : deruikong moves the token on the red edge from to .

The game ends because the token visited every colour on the graph with deruikong making the last move.