408297: GYM103081 J Daisy's Mazes

Daisy enjoys walking in mazes to evacuate the stress of a long day of work. The mazes that she likes are all composed of a set of rooms with one entry room, one exit room, and in each room there are several one-way doors leading to other rooms. Daisy's goal is to find a path from the entry to the exit.

Daisy has a technique to solve mazes. She has noticed that the different doors of any room have different colors and thus she can remember her path by keeping track of the colors of doors along her path. For that, she looks at the plan before entering the maze and builds a deck of colored cards corresponding to the colors of doors she needs to take. Whenever she enters a room, she goes through the door that has the color of the topmost card in her deck and then she discards this card.

It sometimes happens that Daisy's decks are "incomplete" and she arrives in a room with an empty deck or with a topmost card that has a color corresponding to none of the doors. In those cases, Daisy goes through one of the doors in the room and, instead of discarding the topmost card, she adds on top of her deck a card of the color of the door she took.

Let us consider the following example maze with three rooms and three doors: a red door from the entry to room 1, a second red door from room 1 back to the entry, and a blue door between room 1 and the exit. In this example maze (also depicted below) then:

• if Daisy starts with a deck containing a {red} card on top and a {blue} card below, she will go to room 1 and discard the red card, then go to the exit and discard the blue card;
• if Daisy starts with a deck containing a single {red} card then she will necessarily go to room 1 as a first step, discard the red card and from there she can choose to take the {blue} door and exit (it does not matter whether her deck is empty at the end) or she can choose to take the red door and goes back to her initial situation: in the entry room with a single red card;
• if she starts or arrives in the entry room with an empty deck, she will necessarily loop indefinitely. Indeed, the entry has only one door that leads to room 1. Once she arrives in room 1, her deck contains a {red} card on top and thus she has to take the {red} door and discard this card, which leads her back to the entry room with an empty deck.

Daisy knows that, in all of her labyrinths, she can always go from the entry room to the exit room with the right deck. However, some decks do not allow her to escape, whatever the choices she may ever do. She wonders: what is the minimal size of a deck that allows her to escape? Daisy gives you the plan of the maze and asks you to help her determine the minimal size of a deck that allows her go from the entry room to the exit if she makes the right choices.

The first line contains three integers $$$R$$$, $$$D$$$, and $$$C$$$, separated by spaces. $$$R$$$ is the number of rooms, $$$D$$$ is the number of doors, and $$$C$$$ is the number of colors. Rooms are numbered from $$$0$$$ to $$$R-1$$$, and colors are numbered from $$$0$$$ to $$$C-1$$$.

The next $$$D$$$ lines each describes a door with three integers $$$f$$$, $$$t$$$ and $$$c$$$, separated by spaces, and such that $$$0\leq f \leq R-1$$$, $$$0 \leq t \leq R-1$$$, $$$f\neq t$$$, and $$$0\leq c \leq C-1$$$. This indicates that there is a door from room $$$f$$$ to room $$$t$$$, and that this door has color $$$c$$$.

Limits

• $$$2 \leq R \leq 50$$$
• $$$2 \leq D \leq 100$$$
• $$$2 \leq C \leq 20$$$

The output should contain a single line with a single integer: the minimal integer $$$S$$$ such that there is a deck composed of $$$S$$$ cards that allows Daisy, if she makes the right choices, to go from the entry (the room numbered $$$0$$$) to the exit (the room numbered $$$R-1$$$).

4 4 2
0 1 0
1 2 0
2 0 0
1 3 1

0

3 3 2
0 1 1
1 0 1
1 2 0

1

Sample Explanation 1

• Daisy starts in room 0 with an empty deck
• She goes to room 1 with a card 0 on her deck
• She goes to room 2 with an empty deck
• She goes to room 0 with a card 0 on her deck
• She goes to room 1 with an empty deck
• She now has the choice to go the exit.

Sample Explanation 2

This example corresponds to the one given in the text with red represented as 1 and blue as 0.