고속도로

캐나다에는 도시 1부터 도시 N까지 N개의 도시와, 고속도로 1부터 고속도로 N-1까지 N-1개의 고속도로가 있다. 모든 고속도로는 두 도시를 잇고 있으며 양방향으로 통행할 수 있다. 또한 이 고속도로망은 어떤 두 도시든 여러 고속도로를 갈아타고 오갈 수 있도록 설계되어 있다. 다시 말해, N개의 도시와 N-1개의 고속도로는 트리 구조를 이룬다.

정체 정보 센터의 시설장으로 임명된 당신은 이 고속도로망의 정체 정보를 관리해야 한다.

이 시설에서는 N-1개의 고속도로 각각에 대해, 시점 도시에서 종점 도시까지 걸리는 시간 데이터를 관리한다. 예를 들어 아래 그림처럼 도시 1과 도시 3, 도시 3과 도시 4, 도시 2와 도시 3이 고속도로로 연결된 상황이라면, (i, j) = (1, 3), (3, 1), (3, 4), (4, 3), (2, 3), (3, 2) 각각에 대해 "도시 i에서 도시 j까지의 소요 시간"을 이 시설에서 관리한다. 고속도로는 상행과 하행의 소요 시간이 항상 같지는 않다는 점에 유의하라.

이에 더해 이 시설에서는 다음 두 가지 일을 한다.

먼저, 이 시설에는 때때로 "정체 정보"가 들어온다. 정체 정보 1회는 3개의 양의 정수 r, s, t로 주어진다. 이는 "고속도로 r의 상행 소요 시간이 s, 하행 소요 시간이 t이다"라는 뜻이다. 고속도로의 상행이란 그 고속도로의 시점과 종점 도시 중 번호가 작은 도시에서 큰 도시로 향하는 방향을 가리키고, 하행이란 그 반대 방향을 가리킨다. 이 정체 정보에 따라 시설의 데이터를 갱신한다.

또한 이 시설에는 "문의" 전화가 걸려 올 때가 있다. 문의 1회는 2개의 양의 정수 x, y로 주어진다. 이때 시설에서 관리하는 현재 데이터를 바탕으로 "도시 x에서 도시 y까지의 소요 시간"을 계산해 답해야 한다.

어느 하루 동안의 "정체 정보"와 "문의"(이들을 통틀어 쿼리라 한다)의 열이 시각 순으로 주어졌을 때, 각 문의마다 그 답을 출력하는 프로그램을 작성하라. 단, 첫 정체 정보가 들어오기 전 단계에서는 N-1개의 고속도로 모두 소요 시간이 상하행 모두 1이다.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 정수 N과 M이 공백을 구분으로 쓰여 있다.

• 이어지는 N-1개 줄은 1줄에 1개의 고속도로를 기술한다. 이 줄들의 i번째 줄에는 2개의 정수 pi, qi (1 ≤ pi < qi ≤ N)가 공백을 구분으로 쓰여 있으며, 이는 고속도로 i가 도시 pi와 도시 qi를 잇는다는 뜻이다.

• 이어지는 M개 줄은 1줄에 1개의 쿼리(정체 정보 또는 문의)를 기술하며, 다음 둘 중 하나가 쓰여 있다:

  • 정체 정보: 1글자 'I'와 정수 r (1 ≤ r ≤ N-1), s (1 ≤ s ≤ 1,000), t (1 ≤ t ≤ 1,000). 각각은 공백을 구분으로 주어진다.
  • 문의: 1글자 'Q'와 서로 다른 2개의 정수 x (1 ≤ x ≤ N), y (1 ≤ y ≤ N). 각각은 공백을 구분으로 주어진다.

표준 출력에 다음 데이터를 출력한다.

• 출력할 데이터의 줄 수는 입력에 나타나는 글자 'Q'의 개수이다. i번째 줄은 i번째 문의의 답을 나타내는 1개의 정수를 포함한다.

• 2 ≤ N ≤ 100,000 (도시의 수)
• 1 ≤ M ≤ 100,000 (정체 정보의 수와 문의의 수의 합)