Daisy의 미로

Daisy는 긴 하루 업무의 스트레스를 풀려고 미로를 걷는 것을 좋아한다. 그녀가 좋아하는 미로는 방들로 이루어져 있다. 입구 방 하나, 출구 방 하나가 있고, 각 방에는 다른 방으로 이어지는 단방향 문이 여러 개 있다. Daisy의 목표는 입구에서 출구까지 가는 경로를 찾는 것이다.

Daisy에게는 미로를 푸는 방법이 있다. 한 방의 문들은 색이 서로 다르므로, 지나간 문의 색을 기록해 경로를 기억할 수 있다. 미로에 들어가기 전에 그녀는 계획을 살펴보고, 지나야 할 문의 색마다 카드 한 장씩 색 카드 덱을 만든다. 방에 들어갈 때마다 덱 맨 위 카드와 색이 같은 문을 지나고, 그 카드를 버린다.

가끔 Daisy의 덱이 "불완전"할 때가 있다. 덱이 빈 상태로 방에 도착하거나, 맨 위 카드의 색이 어떤 문과도 맞지 않는 방에 도착하는 경우다. 이때 그녀는 그 방의 문 중 하나를 지나고, 맨 위 카드를 버리지 않는 대신 지나간 문의 색 카드를 덱 맨 위에 올린다.

방이 3개, 문이 3개인 다음 미로를 보자. 입구에서 방 1로 가는 빨간 문, 방 1에서 입구로 돌아가는 두 번째 빨간 문, 방 1과 출구 사이의 파란 문이 있다. 이 미로(아래 그림)에서는 다음과 같다.

• Daisy가 맨 위에 빨간 카드, 그 아래에 파란 카드가 있는 덱으로 출발하면, 방 1로 가서 빨간 카드를 버리고, 이어서 출구로 가서 파란 카드를 버린다.
• 빨간 카드 한 장만 있는 덱으로 출발하면, 처음에는 반드시 방 1로 가서 빨간 카드를 버린다. 거기서 파란 문을 지나 출구로 나갈 수도 있고(끝나고 덱이 비어 있는지는 상관없다), 빨간 문을 지나 빨간 카드 한 장을 가진 채 입구로 돌아갈 수도 있다.
• 빈 덱으로 입구 방에서 출발하거나 도착하면 영원히 순환한다. 입구에는 방 1로 가는 문이 하나뿐이다. 방 1에서는 맨 위에 빨간 카드가 있으므로 빨간 문을 지나 그 카드를 버려야 하고, 그 결과 빈 덱으로 입구에 돌아온다.

Daisy는 올바른 덱만 있으면 어떤 미로든 입구에서 출구로 갈 수 있다는 것을 알고 있다. 하지만 어떤 선택을 하더라도 탈출하지 못하게 하는 덱도 있다. 그녀는 탈출을 가능하게 하는 덱의 최소 크기가 얼마인지 궁금해한다. 미로 계획이 주어질 때, Daisy가 올바른 선택을 한다고 가정하고 입구에서 출구로 갈 수 있게 하는 덱의 최소 크기를 구하라.

첫 줄에 공백으로 구분된 정수 세 개 $R$, $D$, $C$가 주어진다. $R$은 방의 개수, $D$는 문의 개수, $C$는 색의 개수이다. 방은 $0$부터 $R-1$까지, 색은 $0$부터 $C-1$까지 번호가 매겨진다.

이어지는 $D$개의 줄에는 각각 공백으로 구분된 정수 $f$, $t$, $c$가 주어진다. 여기서 $0\leq f \leq R-1$, $0 \leq t \leq R-1$, $f\neq t$, $0\leq c \leq C-1$이다. 이는 방 $f$에서 방 $t$로 가는 문이 있고, 그 문의 색이 $c$라는 뜻이다.

한 줄에 정수 하나를 출력한다. Daisy가 올바른 선택을 한다면, $S$장의 카드로 이루어진 덱으로 입구(방 $0$)에서 출구(방 $R-1$)까지 갈 수 있게 하는 최소의 $S$이다.

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