QCC P1 - Quarantine Games

View as PDF

Submit solution

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 N nodes numbered from 1 to N and M edges each coloured red, orange, yellow, green, blue, indigo, or violet. To start the game, a token is placed on node 1, 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, N and M.

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

Output Specification

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

Constraints

2 \le N \le 10^5

1 \le M \le 10^6

C \in \text{{r, o, y, g, b, i, v}}

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 1: piddddgy moves the token on the red edge from 1 to 2.

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

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

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 1: piddddgy moves the token on the blue edge from 1 to 2.

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

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


Comments

There are no comments at the moment.