만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

가슴 속에 무엇인가

시간 제한3초메모리 제한1024 MB

요약
간선이 추가되고 전역 임계값이 바뀌는 그래프에서 두 정점이 연결되는 최대 임계값을 답한다.
난이도

어려움10점 중 9점

유형
유니온 파인드, 분할 정복, 그래프, DFS
정답자
아직 제출이 없습니다

문제

대문 밖을 나서고 입대가 초읽기로 다가오자 초조해진 욱제는 가슴을 마구 내리쳤다. 그러자 평소 심혈관계 건강이 좋지 않았던 욱제의 모세 혈관이 모두 파열됐다.

젊은 욱제의 심혈관계는 1번부터 N번까지 번호가 붙은 N개의 세포와, 서로 다른 두 세포를 연결해 혈액을 공급하는 혈관으로 나타낼 수 있다. 몇 개의 혈관으로 연결된 두 세포 사이에는 혈액이 흐를 수 있다. 욱제가 가슴을 마구 내리쳤기 때문에 처음에는 어떤 혈관도 남아 있지 않다. 시간이 흐르면서 젊은 욱제의 혈관은 생성되고 터지기를 반복한다. 혈관 x의 강도는 한계 심박수 Dx로 나타내는데, 긴장한 욱제의 심박수가 Dx를 초과하면 이 혈관은 견디지 못하고 터진다.

계속 혈관이 생기고 터지면서 멍이 들자, 욱제는 세포 사이에 혈액이 원활하게 공급되는지 걱정되어 자가 진단 기계를 만들려고 한다. 즉, 욱제는 위에 주어진 3가지 쿼리를 처리하는 기계를 만들려고 한다.

  • 1 i j d : i번 세포와 j번 세포를 직접 잇는 한계 심박수 d인 혈관이 생성된다. (i ≠ j) 두 세포 사이에 여러 개의 온전한 혈관이 동시에 존재하는 일은 없다.
  • 2 x : 욱제의 심박수가 순간적으로 x로 변한다. 이 사건이 일어나는 시점 이외에 욱제의 심박수는 충분히 낮아 0으로 가정해도 좋다.
  • 3 i j : 이 쿼리가 주어진 시점에 i번 세포와 j번 세포 사이에 혈액이 흐를 수 있는 욱제의 최대 심박수 x를 출력한다. (i ≠ j)

하지만 욱제는 계속 가슴을 내리치느라 손에 멍이 들어 코딩을 할 수가 없다. 여러분이 이 질문을 대신 처리해 주자.

입력

첫째 줄에 세포의 개수 N과 쿼리의 개수 Q가 주어진다.

둘째 줄부터 Q개의 줄에 걸쳐 쿼리들이 입력으로 주어진다.

출력

3번 쿼리가 주어질 때마다 그에 대한 답을 출력한다. 해당 시점에 두 세포 사이에 혈액이 흐를 수 없다면 0을 출력한다.

제한

  • 2 ≤ N ≤ 316,000
  • 1 ≤ Q ≤ 402,000
  • 1번 쿼리에서 1 ≤ d ≤ 10^9
  • 2번 쿼리에서 1 ≤ x ≤ 10^9
  • 3번 쿼리가 하나 이상 존재한다.
  • 입력의 모든 값은 음 아닌 정수이다.

예제4

  1. 예제 1

    입력
    3 6
1 1 2 100
1 2 3 200
1 1 3 300
3 1 2
3 1 3
3 2 3
    예상 출력
    200
300
200

  2. 예제 2

    입력
    6 9
1 1 2 3
1 2 3 4
1 4 5 5
1 5 6 6
3 1 3
3 1 5
2 4
3 1 3
3 2 3
    예상 출력
    3
0
0
4

  3. 예제 3

    입력
    3 9
1 1 2 9
1 2 3 6
3 1 3
3 1 2
2 7
3 1 3
1 2 3 10
2 9
3 2 3
    예상 출력
    6
9
0
10

  4. 예제 4

    입력
    11 21
1 10 11 57
3 10 11
1 3 11 78
2 100
1 5 11 36
1 10 11 31
3 8 9
1 7 9 29
1 7 10 133
1 7 8 60
3 3 10
1 2 5 90
1 9 11 141
1 8 9 123
3 8 11
3 2 5
2 17
3 2 5
1 6 11 57
1 4 10 127
3 7 11
    예상 출력
    57
0
0
123
90
90
60