비버국에는 N개의 도시와 도시를 잇는 N-1개의 도로가 있다.

현재 모든 도시는 도로를 통해 서로 도달할 수 있는 상태이다.

N-1개의 모든 도로는 다음과 같은 재건을 해야한다.

i번 도시와 j번 도시를 잇는 도로에 대해 다음 4가지 종류의 도로 중 하나로 재건한다.

안타깝게도 비버국의 국토교통부가 비리로 해체되어 재건 계획 문서가 사라졌다.

이에, 비버국의 대통령 비브라스는 유능한 당신에게 복구를 요청하였다.

아무 정보 없이 복구를 할 수는 없기에, 비브라스에게 아래와 같은 추가적인 정보를 요구하였다.

따라서 비브라스는 각 도시의 비버에게 값을 얻어내어 당신에게 알려주었다.

하지만 비리로 물든 비버들이 알려준 값은 확신할 수 없다. 따라서 이 값들이 맞는지 검증을 해야한다!

여기서 "도달할 수 있는" 이라는 정의는, c_1에서 c_k로 도달할 수 있는 상황이라면, c_1도시에서 c_k도시의 경로를 c_1-c_2-...-c_k 라고 했을 때,

1\le x \le k-1 조건 하에, c_x 도시에서 c_{x+1}도시로 갈 수 있음을 의미한다.

또한, 자신의 도시도 도달할 수 있다.

도로 재건 timer 1s memory 1024MB

도로 재건 1s 1024MB