카와이강의 다리

아주 먼 곳에 있는 미드솜머라는 나라에는 귀여운 강 삼각주가 있다. 강에는 진보라색 산성이 흘러서 헤엄칠 수 없다. 삼각주에는 섬이 여러 개 있고, 일부 섬 쌍을 잇는 다리가 있다. 각 다리에는 위험도가 매겨져 있는데, 이는 그 다리를 건너는 것이 얼마나 위험한지를 나타내는 값이며 값이 클수록 더 위험하다.

탐정이면서 우연히도 추리 소설 작가인 리처드 흐라데츠키는 사건을 쫓기 위해 섬 사이를 자주 이동해야 한다. 그는 가능한 모든 경로 중에서 가장 안전한 경로를 선호하는데, 가장 안전한 경로란 경로 위 다리들의 위험도 중 최댓값이 가능한 한 작은 경로를 말한다.

계획을 세우기 위해 리처드는 조사 중인 한 섬에서 다른 섬까지의 가장 안전한 경로를 찾아 달라고 자주 요청한다. 그의 요청을 처리하려면 다음 세 가지 종류의 사건을 계속 기록해야 한다.

• 지역 부족민이 두 섬 사이에 새 다리를 방금 건설했다.
• 크고 분홍색이며 털이 복슬복슬한 산성 곰 루그가 나타나 다리를 파괴한다.
• 리처드가 두 섬 사이의 가장 안전한 경로를 찾아 달라고 요청한다.

입력의 첫 줄에는 두 정수 N과 Q가 주어진다 (2 ≤ N ≤ 105, 1 ≤ Q ≤ 105). N은 섬의 수이고 섬에는 0, 1, ..., N − 1의 번호가 붙어 있으며, Q는 뒤따르는 사건의 수이다.

다음 Q개 줄 각각은 하나의 사건을 나타내며, 세 개 또는 네 개의 정수가 다음과 같이 해석된다.

• 0 X Y V : 위험도 V (0 ≤ V < 10)인 다리가 방금 섬 X와 Y 사이에 건설되었다.
• 1 X Y : 섬 X와 Y를 잇는 다리가 방금 파괴되었다.
• 2 X Y : 리처드가 섬 X에서 섬 Y까지의 가장 안전한 경로가 무엇인지 묻는다.

모든 종류의 사건에서 X와 Y는 유효한 섬 쌍을 나타낸다 (0 ≤ X, Y < N, X ≠ Y). 어느 두 섬 사이에도 다리는 항상 최대 하나만 존재한다. 파괴되는 다리는 그 순간 항상 존재한다.

각각의 2번 사건에 대해, X에서 Y까지의 가장 안전한 경로 위에서 가장 위험한 다리의 위험도를 한 줄에 출력한다. X와 Y 사이에 경로가 없으면 −1을 출력한다.