1번부터 n번까지 번호가 붙은 n개의 배양체를 n-1개의 파이프로 이어 하나의 트리 모양을 만들었습니다. 각 파이프는 A,B,C 3개의 종류 중 하나로 초기에 모든 파이프는 닫혀있습니다.

배양체 중 하나가 바이러스에 감염되어 있습니다. 바이러스에 감염된 배양체는 열린 파이프를 통해 연결된 다른 인접한 배양체를 감염시킵니다.

당신은 종류가 같은 파이프를 한꺼번에 모두 열었다가 닫을 수 있습니다. 단, 한 종류의 파이프를 연 후 다시 닫기 전에 다른 종류의 파이프를 열 수 없습니다. 파이프를 열었다 닫는 행동을 최대 k번 반복해 최대한 많은 배양체에 바이러스를 감염시키려고 합니다.

배양체의 개수를 나타내는 정수 n, 감염된 배양체의 노드 번호를 나타내는 정수 infection, 파이프의 정보를 나타내는 2차원 정수 배열 edges, 최대 행동 수를 나타내는 정수 k가 매개변수로 주어집니다. 최대 k번 파이프를 열었다 닫은 후, 감염된 배양체 개수의 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 2 ≤ n ≤ 100
• 1 ≤ infection ≤ n
• edges의 길이 = n-1
  • edges[i]는 [x, y, type]의 형태로 x번 노드의 배양체와 y번 노드의 배양체 사이가 type 종류의 파이프로 연결되어 있음을 의미합니다.
  • 1 ≤ x < y ≤ n
  • 1 ≤ type ≤ 3
  • 1은 A, 2는 B, 3은 C 를 나타냅니다.
• 1 ≤ k ≤ 10

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

트리가 아래 그림과 같이 구성되어 있습니다.

B 타입 파이프를 열었다 닫은 후, A 타입 파이프를 열었다 닫으면 감염된 배양체가 총 6개가 됩니다.

1. B 타입 파이프 열림 : [1 - 5, 2 - 9]를 연결하는 파이프가 열립니다. 배양체 #5가 감염됩니다.
2. B 타입 파이프 닫힘
3. A 타입 파이프 열림 : [1 - 2, 1 - 3, 5 - 6, 5 - 7, 9 - 10]을 연결하는 파이프가 열립니다. 배양체 #2, #3, #6, #7이 감염됩니다.
4. A 타입 파이프 닫힘
5. 최종적으로 감염된 배양체는 #1, #2, #3, #5, #6, #7입니다.

2번의 행동으로 감염된 배양체가 6개보다 많아지는 방법은 없습니다. 따라서 6을 return 해야 합니다.

입출력 예 #2

트리가 아래 그림과 같이 구성되어 있습니다.

ABC 혹은 ACB 혹은 BAC 순으로 파이프를 열었다 닫으면 감염된 배양체가 총 7개가 됩니다.
3번의 행동으로 감염된 배양체가 7개보다 많아지는 방법은 없습니다. 따라서 7을 return 해야 합니다.