; LLVM IR from ShahjalalShohag/code-library :: Graph Theory/Directed MST.ll (Z4DMSTiiRKSt6vectorI4edgeSaIS0_EE)

; Unoptimized IR (clang -disable-llvm-passes):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%"class.std::vector" = type { %"struct.std::_Vector_base" }
%"struct.std::_Vector_base" = type { %"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl" }
%"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl" = type { %"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl_data" }
%"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl_data" = type { ptr, ptr, ptr }
%"class.std::allocator" = type { i8 }
%"class.__gnu_cxx::__normal_iterator" = type { ptr }
%struct.edge = type { i32, i32, i64 }
%struct.DSU = type { %"class.std::vector" }
%"class.__gnu_cxx::__normal_iterator.5" = type { ptr }
%"class.std::queue" = type { %"class.std::deque" }
%"class.std::deque" = type { %"class.std::_Deque_base" }
%"class.std::_Deque_base" = type { %"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl" }
%"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl" = type { %"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl_data" }
%"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl_data" = type { ptr, i64, %"struct.std::_Deque_iterator", %"struct.std::_Deque_iterator" }
%"struct.std::_Deque_iterator" = type { ptr, ptr, ptr, ptr }
%struct.PQ = type { i64, %"class.std::priority_queue" }
%"class.std::priority_queue" = type <{ %"class.std::vector.0", [8 x i8] }>
%"class.std::vector.0" = type { %"struct.std::_Vector_base.1" }
%"struct.std::_Vector_base.1" = type { %"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl" }
%"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl" = type { %"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl_data" }
%"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl_data" = type { ptr, ptr, ptr }

@.str = external hidden unnamed_addr constant [11 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [92 x i8], align 1
@__PRETTY_FUNCTION__._Z4DMSTiiRKSt6vectorI4edgeSaIS0_EE = external hidden unnamed_addr constant [49 x i8], align 1

; Function Attrs: mustprogress uwtable
define dso_local void @_Z4DMSTiiRKSt6vectorI4edgeSaIS0_EE(ptr dead_on_unwind noalias writable sret(%"class.std::vector") align 8 %0, i32 noundef %1, i32 noundef %2, ptr noundef nonnull align 8 dereferenceable(24) %3) #0 personality ptr @__gxx_personality_v0 {
  %5 = alloca ptr, align 8
  %6 = alloca i32, align 4
  %7 = alloca i32, align 4
  %8 = alloca ptr, align 8
  %9 = alloca %"class.std::vector", align 8
  %10 = alloca i32, align 4
  %11 = alloca %"class.std::allocator", align 1
  %12 = alloca ptr, align 8
  %13 = alloca i32, align 4
  %14 = alloca %"class.std::vector", align 8
  %15 = alloca i32, align 4
  %16 = alloca %"class.std::allocator", align 1
  %17 = alloca ptr, align 8
  %18 = alloca i64, align 8
  %19 = alloca i64, align 8
  %20 = alloca i64, align 8
  %21 = alloca ptr, align 8
  %22 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %23 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %24 = alloca %struct.edge, align 8
  %25 = alloca %struct.edge, align 8
  %26 = alloca i32, align 4
  %27 = alloca %struct.edge, align 8
  %28 = alloca i32, align 4
  %29 = alloca %struct.DSU, align 8
  %30 = alloca i32, align 4
  %31 = alloca %struct.edge, align 8
  %32 = alloca i32, align 4
  %33 = alloca i32, align 4
  %34 = alloca i32, align 4
  %35 = alloca ptr, align 8
  %36 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  %37 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  %38 = alloca i32, align 4
  %39 = alloca i1, align 1
  %40 = alloca i32, align 4
  %41 = alloca %"class.std::allocator", align 1
  %42 = alloca %"class.std::queue", align 8
  %43 = alloca i32, align 4
  %44 = alloca ptr, align 8
  %45 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  %46 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  %47 = alloca i32, align 4
  store ptr %0, ptr %5, align 8
  store i32 %1, ptr %6, align 4, !tbaa !5
  store i32 %2, ptr %7, align 4, !tbaa !5
  store ptr %3, ptr %8, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 24, ptr %9) #8
  %48 = load i32, ptr %6, align 4, !tbaa !5
  %49 = mul nsw i32 2, %48
  %50 = sub nsw i32 %49, 1
  %51 = sext i32 %50 to i64
  call void @llvm.lifetime.start.p0(i64 4, ptr %10) #8
  store i32 -1, ptr %10, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 1, ptr %11) #8
  call void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1) %11) #8
  invoke void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %51, ptr noundef nonnull align 4 dereferenceable(4) %10, ptr noundef nonnull align 1 dereferenceable(1) %11)
          to label %52 unwind label %101

52:                                               ; preds = %4
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %11) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr %11) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %10) #8
  call void @llvm.lifetime.start.p0(i64 24, ptr %14) #8
  %53 = load i32, ptr %6, align 4, !tbaa !5
  %54 = mul nsw i32 2, %53
  %55 = sub nsw i32 %54, 1
  %56 = sext i32 %55 to i64
  call void @llvm.lifetime.start.p0(i64 4, ptr %15) #8
  store i32 -1, ptr %15, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 1, ptr %16) #8
  call void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1) %16) #8
  invoke void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24) %14, i64 noundef %56, ptr noundef nonnull align 4 dereferenceable(4) %15, ptr noundef nonnull align 1 dereferenceable(1) %16)
          to label %57 unwind label %105

57:                                               ; preds = %52
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %16) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr %16) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %15) #8
  %58 = load i32, ptr %6, align 4, !tbaa !5
  %59 = mul nsw i32 2, %58
  %60 = sub nsw i32 %59, 1
  %61 = zext i32 %60 to i64
  %62 = call ptr @llvm.stacksave.p0()
  store ptr %62, ptr %17, align 8
  %63 = alloca %struct.edge, i64 %61, align 16
  store i64 %61, ptr %18, align 8
  %64 = load i32, ptr %6, align 4, !tbaa !5
  %65 = mul nsw i32 2, %64
  %66 = sub nsw i32 %65, 1
  %67 = zext i32 %66 to i64
  %68 = alloca %"class.std::vector", i64 %67, align 16
  store i64 %67, ptr %19, align 8
  %69 = icmp eq i64 %67, 0
  br i1 %69, label %76, label %70

70:                                               ; preds = %57
  %71 = getelementptr inbounds %"class.std::vector", ptr %68, i64 %67
  br label %72

72:                                               ; preds = %72, %70
  %73 = phi ptr [ %68, %70 ], [ %74, %72 ]
  call void @_ZNSt6vectorIiSaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(24) %73) #8
  %74 = getelementptr inbounds %"class.std::vector", ptr %73, i64 1
  %75 = icmp eq ptr %74, %71
  br i1 %75, label %76, label %72

76:                                               ; preds = %72, %57
  %77 = load i32, ptr %6, align 4, !tbaa !5
  %78 = mul nsw i32 2, %77
  %79 = sub nsw i32 %78, 1
  %80 = zext i32 %79 to i64
  %81 = alloca %struct.PQ, i64 %80, align 16
  store i64 %80, ptr %20, align 8
  %82 = icmp eq i64 %80, 0
  br i1 %82, label %90, label %83

83:                                               ; preds = %76
  %84 = getelementptr inbounds %struct.PQ, ptr %81, i64 %80
  br label %85

85:                                               ; preds = %87, %83
  %86 = phi ptr [ %81, %83 ], [ %88, %87 ]
  invoke void @_ZN2PQI4edgeEC2Ev(ptr noundef nonnull align 8 dereferenceable(40) %86)
          to label %87 unwind label %109

87:                                               ; preds = %85
  %88 = getelementptr inbounds %struct.PQ, ptr %86, i64 1
  %89 = icmp eq ptr %88, %84
  br i1 %89, label %90, label %85

90:                                               ; preds = %87, %76
  call void @llvm.lifetime.start.p0(i64 8, ptr %21) #8
  %91 = load ptr, ptr %8, align 8, !tbaa !9
  store ptr %91, ptr %21, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 8, ptr %22) #8
  %92 = load ptr, ptr %21, align 8, !tbaa !9
  %93 = call ptr @_ZNKSt6vectorI4edgeSaIS0_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %92) #8
  %94 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %22, i32 0, i32 0
  store ptr %93, ptr %94, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr %23) #8
  %95 = load ptr, ptr %21, align 8, !tbaa !9
  %96 = call ptr @_ZNKSt6vectorI4edgeSaIS0_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %95) #8
  %97 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %23, i32 0, i32 0
  store ptr %96, ptr %97, align 8
  br label %98

98:                                               ; preds = %130, %90
  %99 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPK4edgeSt6vectorIS1_SaIS1_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8) %22, ptr noundef nonnull align 8 dereferenceable(8) %23) #8
  br i1 %99, label %119, label %100

100:                                              ; preds = %98
  call void @llvm.lifetime.end.p0(i64 8, ptr %23) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %22) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %21) #8
  br label %136

101:                                              ; preds = %4
  %102 = landingpad { ptr, i32 }
          cleanup
  %103 = extractvalue { ptr, i32 } %102, 0
  store ptr %103, ptr %12, align 8
  %104 = extractvalue { ptr, i32 } %102, 1
  store i32 %104, ptr %13, align 4
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %11) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr %11) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %10) #8
  br label %460

105:                                              ; preds = %52
  %106 = landingpad { ptr, i32 }
          cleanup
  %107 = extractvalue { ptr, i32 } %106, 0
  store ptr %107, ptr %12, align 8
  %108 = extractvalue { ptr, i32 } %106, 1
  store i32 %108, ptr %13, align 4
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %16) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr %16) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %15) #8
  br label %459

109:                                              ; preds = %85
  %110 = landingpad { ptr, i32 }
          cleanup
  %111 = extractvalue { ptr, i32 } %110, 0
  store ptr %111, ptr %12, align 8
  %112 = extractvalue { ptr, i32 } %110, 1
  store i32 %112, ptr %13, align 4
  %113 = icmp eq ptr %81, %86
  br i1 %113, label %118, label %114

114:                                              ; preds = %114, %109
  %115 = phi ptr [ %86, %109 ], [ %116, %114 ]
  %116 = getelementptr inbounds %struct.PQ, ptr %115, i64 -1
  call void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40) %116) #8
  %117 = icmp eq ptr %116, %81
  br i1 %117, label %118, label %114

118:                                              ; preds = %114, %109
  br label %451

119:                                              ; preds = %98
  call void @llvm.lifetime.start.p0(i64 16, ptr %24) #8
  %120 = call noundef nonnull align 8 dereferenceable(16) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %22) #8
  call void @llvm.memcpy.p0.p0.i64(ptr align 8 %24, ptr align 8 %120, i64 16, i1 false), !tbaa.struct !11
  %121 = getelementptr inbounds %struct.edge, ptr %24, i32 0, i32 1
  %122 = load i32, ptr %121, align 4, !tbaa !14
  %123 = sext i32 %122 to i64
  %124 = getelementptr inbounds %struct.PQ, ptr %81, i64 %123
  call void @llvm.memcpy.p0.p0.i64(ptr align 8 %25, ptr align 8 %24, i64 16, i1 false), !tbaa.struct !11
  %125 = getelementptr inbounds { i64, i64 }, ptr %25, i32 0, i32 0
  %126 = load i64, ptr %125, align 8
  %127 = getelementptr inbounds { i64, i64 }, ptr %25, i32 0, i32 1
  %128 = load i64, ptr %127, align 8
  invoke void @_ZN2PQI4edgeE4pushES0_(ptr noundef nonnull align 8 dereferenceable(40) %124, i64 %126, i64 %128)
          to label %129 unwind label %132

129:                                              ; preds = %119
  call void @llvm.lifetime.end.p0(i64 16, ptr %24) #8
  br label %130

130:                                              ; preds = %129
  %131 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %22) #8
  br label %98

132:                                              ; preds = %119
  %133 = landingpad { ptr, i32 }
          cleanup
  %134 = extractvalue { ptr, i32 } %133, 0
  store ptr %134, ptr %12, align 8
  %135 = extractvalue { ptr, i32 } %133, 1
  store i32 %135, ptr %13, align 4
  call void @llvm.lifetime.end.p0(i64 16, ptr %24) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %23) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %22) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %21) #8
  br label %437

136:                                              ; preds = %100
  call void @llvm.lifetime.start.p0(i64 4, ptr %26) #8
  store i32 0, ptr %26, align 4, !tbaa !5
  br label %137

137:                                              ; preds = %162, %136
  %138 = load i32, ptr %26, align 4, !tbaa !5
  %139 = load i32, ptr %6, align 4, !tbaa !5
  %140 = icmp slt i32 %138, %139
  br i1 %140, label %142, label %141

141:                                              ; preds = %137
  call void @llvm.lifetime.end.p0(i64 4, ptr %26) #8
  br label %169

142:                                              ; preds = %137
  %143 = load i32, ptr %26, align 4, !tbaa !5
  %144 = add nsw i32 %143, 1
  %145 = load i32, ptr %6, align 4, !tbaa !5
  %146 = srem i32 %144, %145
  %147 = sext i32 %146 to i64
  %148 = getelementptr inbounds %struct.PQ, ptr %81, i64 %147
  %149 = getelementptr inbounds %struct.edge, ptr %27, i32 0, i32 0
  %150 = load i32, ptr %26, align 4, !tbaa !5
  store i32 %150, ptr %149, align 8, !tbaa !16
  %151 = getelementptr inbounds %struct.edge, ptr %27, i32 0, i32 1
  %152 = load i32, ptr %26, align 4, !tbaa !5
  %153 = add nsw i32 %152, 1
  %154 = load i32, ptr %6, align 4, !tbaa !5
  %155 = srem i32 %153, %154
  store i32 %155, ptr %151, align 4, !tbaa !14
  %156 = getelementptr inbounds %struct.edge, ptr %27, i32 0, i32 2
  store i64 1000000000000000000, ptr %156, align 8, !tbaa !17
  %157 = getelementptr inbounds { i64, i64 }, ptr %27, i32 0, i32 0
  %158 = load i64, ptr %157, align 8
  %159 = getelementptr inbounds { i64, i64 }, ptr %27, i32 0, i32 1
  %160 = load i64, ptr %159, align 8
  invoke void @_ZN2PQI4edgeE4pushES0_(ptr noundef nonnull align 8 dereferenceable(40) %148, i64 %158, i64 %160)
          to label %161 unwind label %165

161:                                              ; preds = %142
  br label %162

162:                                              ; preds = %161
  %163 = load i32, ptr %26, align 4, !tbaa !5
  %164 = add nsw i32 %163, 1
  store i32 %164, ptr %26, align 4, !tbaa !5
  br label %137, !llvm.loop !18

165:                                              ; preds = %142
  %166 = landingpad { ptr, i32 }
          cleanup
  %167 = extractvalue { ptr, i32 } %166, 0
  store ptr %167, ptr %12, align 8
  %168 = extractvalue { ptr, i32 } %166, 1
  store i32 %168, ptr %13, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %26) #8
  br label %437

169:                                              ; preds = %141
  call void @llvm.lifetime.start.p0(i64 4, ptr %28) #8
  %170 = load i32, ptr %6, align 4, !tbaa !5
  store i32 %170, ptr %28, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 24, ptr %29) #8
  %171 = load i32, ptr %6, align 4, !tbaa !5
  %172 = mul nsw i32 2, %171
  %173 = sub nsw i32 %172, 1
  invoke void @_ZN3DSUC2Ei(ptr noundef nonnull align 8 dereferenceable(24) %29, i32 noundef %173)
          to label %174 unwind label %200

174:                                              ; preds = %169
  call void @llvm.lifetime.start.p0(i64 4, ptr %30) #8
  store i32 0, ptr %30, align 4, !tbaa !5
  br label %175

175:                                              ; preds = %314, %312, %174
  %176 = load i32, ptr %30, align 4, !tbaa !5
  %177 = sext i32 %176 to i64
  %178 = getelementptr inbounds %struct.PQ, ptr %81, i64 %177
  %179 = invoke noundef i32 @_ZN2PQI4edgeE4sizeEv(ptr noundef nonnull align 8 dereferenceable(40) %178)
          to label %180 unwind label %204

180:                                              ; preds = %175
  %181 = icmp ne i32 %179, 0
  br i1 %181, label %182, label %317

182:                                              ; preds = %180
  call void @llvm.lifetime.start.p0(i64 16, ptr %31) #8
  %183 = load i32, ptr %30, align 4, !tbaa !5
  %184 = sext i32 %183 to i64
  %185 = getelementptr inbounds %struct.PQ, ptr %81, i64 %184
  %186 = invoke { i64, i64 } @_ZN2PQI4edgeE3popEv(ptr noundef nonnull align 8 dereferenceable(40) %185)
          to label %187 unwind label %208

187:                                              ; preds = %182
  %188 = getelementptr inbounds { i64, i64 }, ptr %31, i32 0, i32 0
  %189 = extractvalue { i64, i64 } %186, 0
  store i64 %189, ptr %188, align 8
  %190 = getelementptr inbounds { i64, i64 }, ptr %31, i32 0, i32 1
  %191 = extractvalue { i64, i64 } %186, 1
  store i64 %191, ptr %190, align 8
  call void @llvm.lifetime.start.p0(i64 4, ptr %32) #8
  %192 = getelementptr inbounds %struct.edge, ptr %31, i32 0, i32 0
  %193 = load i32, ptr %192, align 8, !tbaa !16
  %194 = invoke noundef i32 @_ZN3DSU4rootEi(ptr noundef nonnull align 8 dereferenceable(24) %29, i32 noundef %193)
          to label %195 unwind label %212

195:                                              ; preds = %187
  store i32 %194, ptr %32, align 4, !tbaa !5
  %196 = load i32, ptr %32, align 4, !tbaa !5
  %197 = load i32, ptr %30, align 4, !tbaa !5
  %198 = icmp eq i32 %196, %197
  br i1 %198, label %199, label %216

199:                                              ; preds = %195
  store i32 7, ptr %33, align 4
  br label %312, !llvm.loop !20

200:                                              ; preds = %169
  %201 = landingpad { ptr, i32 }
          cleanup
  %202 = extractvalue { ptr, i32 } %201, 0
  store ptr %202, ptr %12, align 8
  %203 = extractvalue { ptr, i32 } %201, 1
  store i32 %203, ptr %13, align 4
  br label %429

204:                                              ; preds = %175
  %205 = landingpad { ptr, i32 }
          cleanup
  %206 = extractvalue { ptr, i32 } %205, 0
  store ptr %206, ptr %12, align 8
  %207 = extractvalue { ptr, i32 } %205, 1
  store i32 %207, ptr %13, align 4
  br label %428

208:                                              ; preds = %182
  %209 = landingpad { ptr, i32 }
          cleanup
  %210 = extractvalue { ptr, i32 } %209, 0
  store ptr %210, ptr %12, align 8
  %211 = extractvalue { ptr, i32 } %209, 1
  store i32 %211, ptr %13, align 4
  br label %316

212:                                              ; preds = %187
  %213 = landingpad { ptr, i32 }
          cleanup
  %214 = extractvalue { ptr, i32 } %213, 0
  store ptr %214, ptr %12, align 8
  %215 = extractvalue { ptr, i32 } %213, 1
  store i32 %215, ptr %13, align 4
  br label %315

216:                                              ; preds = %195
  %217 = load i32, ptr %32, align 4, !tbaa !5
  %218 = load i32, ptr %30, align 4, !tbaa !5
  %219 = sext i32 %218 to i64
  %220 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %219) #8
  store i32 %217, ptr %220, align 4, !tbaa !5
  %221 = load i32, ptr %30, align 4, !tbaa !5
  %222 = sext i32 %221 to i64
  %223 = getelementptr inbounds %struct.edge, ptr %63, i64 %222
  call void @llvm.memcpy.p0.p0.i64(ptr align 16 %223, ptr align 8 %31, i64 16, i1 false), !tbaa.struct !11
  %224 = load i32, ptr %32, align 4, !tbaa !5
  %225 = sext i32 %224 to i64
  %226 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %225) #8
  %227 = load i32, ptr %226, align 4, !tbaa !5
  %228 = icmp eq i32 %227, -1
  br i1 %228, label %229, label %231

229:                                              ; preds = %216
  %230 = load i32, ptr %32, align 4, !tbaa !5
  store i32 %230, ptr %30, align 4, !tbaa !5
  br label %311

231:                                              ; preds = %216
  call void @llvm.lifetime.start.p0(i64 4, ptr %34) #8
  %232 = load i32, ptr %32, align 4, !tbaa !5
  store i32 %232, ptr %34, align 4, !tbaa !5
  br label %233

233:                                              ; preds = %274, %231
  %234 = load i32, ptr %34, align 4, !tbaa !5
  %235 = sext i32 %234 to i64
  %236 = getelementptr inbounds %struct.PQ, ptr %81, i64 %235
  %237 = load i32, ptr %34, align 4, !tbaa !5
  %238 = sext i32 %237 to i64
  %239 = getelementptr inbounds %struct.edge, ptr %63, i64 %238
  %240 = getelementptr inbounds %struct.edge, ptr %239, i32 0, i32 2
  %241 = load i64, ptr %240, align 8, !tbaa !17
  %242 = sub nsw i64 0, %241
  invoke void @_ZN2PQI4edgeE3addEx(ptr noundef nonnull align 8 dereferenceable(40) %236, i64 noundef %242)
          to label %243 unwind label %258

243:                                              ; preds = %233
  %244 = load i32, ptr %28, align 4, !tbaa !5
  %245 = sext i32 %244 to i64
  %246 = getelementptr inbounds %struct.PQ, ptr %81, i64 %245
  %247 = load i32, ptr %34, align 4, !tbaa !5
  %248 = sext i32 %247 to i64
  %249 = getelementptr inbounds %struct.PQ, ptr %81, i64 %248
  invoke void @_ZN2PQI4edgeE5mergeEOS1_(ptr noundef nonnull align 8 dereferenceable(40) %246, ptr noundef nonnull align 8 dereferenceable(40) %249)
          to label %250 unwind label %258

250:                                              ; preds = %243
  %251 = load i32, ptr %34, align 4, !tbaa !5
  %252 = sext i32 %251 to i64
  %253 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %252) #8
  %254 = load i32, ptr %253, align 4, !tbaa !5
  %255 = icmp ne i32 %254, -1
  br i1 %255, label %256, label %257

256:                                              ; preds = %250
  br label %263

257:                                              ; preds = %250
  call void @__assert_fail(ptr noundef @.str, ptr noundef @.str.1, i32 noundef 63, ptr noundef @__PRETTY_FUNCTION__._Z4DMSTiiRKSt6vectorI4edgeSaIS0_EE) #9
  unreachable

258:                                              ; preds = %267, %263, %243, %233
  %259 = landingpad { ptr, i32 }
          cleanup
  %260 = extractvalue { ptr, i32 } %259, 0
  store ptr %260, ptr %12, align 8
  %261 = extractvalue { ptr, i32 } %259, 1
  store i32 %261, ptr %13, align 4
  br label %310

262:                                              ; No predecessors!
  br label %263

263:                                              ; preds = %262, %256
  %264 = load i32, ptr %28, align 4, !tbaa !5
  %265 = sext i32 %264 to i64
  %266 = getelementptr inbounds %"class.std::vector", ptr %68, i64 %265
  invoke void @_ZNSt6vectorIiSaIiEE9push_backERKi(ptr noundef nonnull align 8 dereferenceable(24) %266, ptr noundef nonnull align 4 dereferenceable(4) %34)
          to label %267 unwind label %258

267:                                              ; preds = %263
  %268 = load i32, ptr %34, align 4, !tbaa !5
  %269 = sext i32 %268 to i64
  %270 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %269) #8
  %271 = load i32, ptr %270, align 4, !tbaa !5
  %272 = invoke noundef i32 @_ZN3DSU4rootEi(ptr noundef nonnull align 8 dereferenceable(24) %29, i32 noundef %271)
          to label %273 unwind label %258

273:                                              ; preds = %267
  store i32 %272, ptr %34, align 4, !tbaa !5
  br label %274

274:                                              ; preds = %273
  %275 = load i32, ptr %34, align 4, !tbaa !5
  %276 = load i32, ptr %32, align 4, !tbaa !5
  %277 = icmp ne i32 %275, %276
  br i1 %277, label %233, label %278, !llvm.loop !21

278:                                              ; preds = %274
  call void @llvm.lifetime.start.p0(i64 8, ptr %35) #8
  %279 = load i32, ptr %28, align 4, !tbaa !5
  %280 = sext i32 %279 to i64
  %281 = getelementptr inbounds %"class.std::vector", ptr %68, i64 %280
  store ptr %281, ptr %35, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 8, ptr %36) #8
  %282 = load ptr, ptr %35, align 8, !tbaa !9
  %283 = call ptr @_ZNSt6vectorIiSaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %282) #8
  %284 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator.5", ptr %36, i32 0, i32 0
  store ptr %283, ptr %284, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr %37) #8
  %285 = load ptr, ptr %35, align 8, !tbaa !9
  %286 = call ptr @_ZNSt6vectorIiSaIiEE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %285) #8
  %287 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator.5", ptr %37, i32 0, i32 0
  store ptr %286, ptr %287, align 8
  br label %288

288:                                              ; preds = %301, %278
  %289 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8) %36, ptr noundef nonnull align 8 dereferenceable(8) %37) #8
  br i1 %289, label %291, label %290

290:                                              ; preds = %288
  store i32 11, ptr %33, align 4
  call void @llvm.lifetime.end.p0(i64 8, ptr %37) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %36) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %35) #8
  br label %307

291:                                              ; preds = %288
  call void @llvm.lifetime.start.p0(i64 4, ptr %38) #8
  %292 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %36) #8
  %293 = load i32, ptr %292, align 4, !tbaa !5
  store i32 %293, ptr %38, align 4, !tbaa !5
  %294 = load i32, ptr %28, align 4, !tbaa !5
  %295 = load i32, ptr %38, align 4, !tbaa !5
  %296 = sext i32 %295 to i64
  %297 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %14, i64 noundef %296) #8
  store i32 %294, ptr %297, align 4, !tbaa !5
  %298 = load i32, ptr %38, align 4, !tbaa !5
  %299 = load i32, ptr %28, align 4, !tbaa !5
  invoke void @_ZN3DSU7set_parEii(ptr noundef nonnull align 8 dereferenceable(24) %29, i32 noundef %298, i32 noundef %299)
          to label %300 unwind label %303

300:                                              ; preds = %291
  call void @llvm.lifetime.end.p0(i64 4, ptr %38) #8
  br label %301

301:                                              ; preds = %300
  %302 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %36) #8
  br label %288

303:                                              ; preds = %291
  %304 = landingpad { ptr, i32 }
          cleanup
  %305 = extractvalue { ptr, i32 } %304, 0
  store ptr %305, ptr %12, align 8
  %306 = extractvalue { ptr, i32 } %304, 1
  store i32 %306, ptr %13, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %38) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %37) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %36) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %35) #8
  br label %310

307:                                              ; preds = %290
  %308 = load i32, ptr %28, align 4, !tbaa !5
  %309 = add nsw i32 %308, 1
  store i32 %309, ptr %28, align 4, !tbaa !5
  store i32 %308, ptr %30, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %34) #8
  br label %311

310:                                              ; preds = %303, %258
  call void @llvm.lifetime.end.p0(i64 4, ptr %34) #8
  br label %315

311:                                              ; preds = %307, %229
  store i32 0, ptr %33, align 4
  br label %312

312:                                              ; preds = %311, %199
  call void @llvm.lifetime.end.p0(i64 4, ptr %32) #8
  call void @llvm.lifetime.end.p0(i64 16, ptr %31) #8
  %313 = load i32, ptr %33, align 4
  switch i32 %313, label %466 [
    i32 0, label %314
    i32 7, label %175
  ]

314:                                              ; preds = %312
  br label %175, !llvm.loop !20

315:                                              ; preds = %310, %212
  call void @llvm.lifetime.end.p0(i64 4, ptr %32) #8
  br label %316

316:                                              ; preds = %315, %208
  call void @llvm.lifetime.end.p0(i64 16, ptr %31) #8
  br label %428

317:                                              ; preds = %180
  store i1 false, ptr %39, align 1
  %318 = load i32, ptr %6, align 4, !tbaa !5
  %319 = mul nsw i32 2, %318
  %320 = sub nsw i32 %319, 1
  %321 = sext i32 %320 to i64
  call void @llvm.lifetime.start.p0(i64 4, ptr %40) #8
  store i32 -1, ptr %40, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 1, ptr %41) #8
  call void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1) %41) #8
  invoke void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %321, ptr noundef nonnull align 4 dereferenceable(4) %40, ptr noundef nonnull align 1 dereferenceable(1) %41)
          to label %322 unwind label %356

322:                                              ; preds = %317
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %41) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr %41) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %40) #8
  call void @llvm.lifetime.start.p0(i64 80, ptr %42) #8
  invoke void @_ZNSt5queueIiSt5dequeIiSaIiEEEC2IS2_vEEv(ptr noundef nonnull align 8 dereferenceable(80) %42)
          to label %323 unwind label %360

323:                                              ; preds = %322
  invoke void @_ZNSt5queueIiSt5dequeIiSaIiEEE4pushERKi(ptr noundef nonnull align 8 dereferenceable(80) %42, ptr noundef nonnull align 4 dereferenceable(4) %7)
          to label %324 unwind label %364

324:                                              ; preds = %323
  br label %325

325:                                              ; preds = %411, %324
  %326 = invoke noundef i64 @_ZNKSt5queueIiSt5dequeIiSaIiEEE4sizeEv(ptr noundef nonnull align 8 dereferenceable(80) %42)
          to label %327 unwind label %364

327:                                              ; preds = %325
  %328 = icmp ne i64 %326, 0
  br i1 %328, label %329, label %413

329:                                              ; preds = %327
  call void @llvm.lifetime.start.p0(i64 4, ptr %43) #8
  %330 = invoke noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt5queueIiSt5dequeIiSaIiEEE5frontEv(ptr noundef nonnull align 8 dereferenceable(80) %42)
          to label %331 unwind label %368

331:                                              ; preds = %329
  %332 = load i32, ptr %330, align 4, !tbaa !5
  store i32 %332, ptr %43, align 4, !tbaa !5
  invoke void @_ZNSt5queueIiSt5dequeIiSaIiEEE3popEv(ptr noundef nonnull align 8 dereferenceable(80) %42)
          to label %333 unwind label %368

333:                                              ; preds = %331
  br label %334

334:                                              ; preds = %406, %333
  %335 = load i32, ptr %43, align 4, !tbaa !5
  %336 = sext i32 %335 to i64
  %337 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %14, i64 noundef %336) #8
  %338 = load i32, ptr %337, align 4, !tbaa !5
  %339 = icmp ne i32 %338, -1
  br i1 %339, label %340, label %411

340:                                              ; preds = %334
  call void @llvm.lifetime.start.p0(i64 8, ptr %44) #8
  %341 = load i32, ptr %43, align 4, !tbaa !5
  %342 = sext i32 %341 to i64
  %343 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %14, i64 noundef %342) #8
  %344 = load i32, ptr %343, align 4, !tbaa !5
  %345 = sext i32 %344 to i64
  %346 = getelementptr inbounds %"class.std::vector", ptr %68, i64 %345
  store ptr %346, ptr %44, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 8, ptr %45) #8
  %347 = load ptr, ptr %44, align 8, !tbaa !9
  %348 = call ptr @_ZNSt6vectorIiSaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %347) #8
  %349 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator.5", ptr %45, i32 0, i32 0
  store ptr %348, ptr %349, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr %46) #8
  %350 = load ptr, ptr %44, align 8, !tbaa !9
  %351 = call ptr @_ZNSt6vectorIiSaIiEE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %350) #8
  %352 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator.5", ptr %46, i32 0, i32 0
  store ptr %351, ptr %352, align 8
  br label %353

353:                                              ; preds = %404, %340
  %354 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8) %45, ptr noundef nonnull align 8 dereferenceable(8) %46) #8
  br i1 %354, label %372, label %355

355:                                              ; preds = %353
  store i32 17, ptr %33, align 4
  call void @llvm.lifetime.end.p0(i64 8, ptr %46) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %45) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %44) #8
  br label %406

356:                                              ; preds = %317
  %357 = landingpad { ptr, i32 }
          cleanup
  %358 = extractvalue { ptr, i32 } %357, 0
  store ptr %358, ptr %12, align 8
  %359 = extractvalue { ptr, i32 } %357, 1
  store i32 %359, ptr %13, align 4
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %41) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr %41) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %40) #8
  br label %428

360:                                              ; preds = %322
  %361 = landingpad { ptr, i32 }
          cleanup
  %362 = extractvalue { ptr, i32 } %361, 0
  store ptr %362, ptr %12, align 8
  %363 = extractvalue { ptr, i32 } %361, 1
  store i32 %363, ptr %13, align 4
  br label %423

364:                                              ; preds = %413, %325, %323
  %365 = landingpad { ptr, i32 }
          cleanup
  %366 = extractvalue { ptr, i32 } %365, 0
  store ptr %366, ptr %12, align 8
  %367 = extractvalue { ptr, i32 } %365, 1
  store i32 %367, ptr %13, align 4
  br label %422

368:                                              ; preds = %331, %329
  %369 = landingpad { ptr, i32 }
          cleanup
  %370 = extractvalue { ptr, i32 } %369, 0
  store ptr %370, ptr %12, align 8
  %371 = extractvalue { ptr, i32 } %369, 1
  store i32 %371, ptr %13, align 4
  br label %412

372:                                              ; preds = %353
  call void @llvm.lifetime.start.p0(i64 4, ptr %47) #8
  %373 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %45) #8
  %374 = load i32, ptr %373, align 4, !tbaa !5
  store i32 %374, ptr %47, align 4, !tbaa !5
  %375 = load i32, ptr %47, align 4, !tbaa !5
  %376 = load i32, ptr %43, align 4, !tbaa !5
  %377 = icmp ne i32 %375, %376
  br i1 %377, label %378, label %403

378:                                              ; preds = %372
  %379 = load i32, ptr %47, align 4, !tbaa !5
  %380 = sext i32 %379 to i64
  %381 = getelementptr inbounds %struct.edge, ptr %63, i64 %380
  %382 = getelementptr inbounds %struct.edge, ptr %381, i32 0, i32 0
  %383 = load i32, ptr %382, align 16, !tbaa !16
  %384 = load i32, ptr %47, align 4, !tbaa !5
  %385 = sext i32 %384 to i64
  %386 = getelementptr inbounds %struct.edge, ptr %63, i64 %385
  %387 = getelementptr inbounds %struct.edge, ptr %386, i32 0, i32 1
  %388 = load i32, ptr %387, align 4, !tbaa !14
  %389 = sext i32 %388 to i64
  %390 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %389) #8
  store i32 %383, ptr %390, align 4, !tbaa !5
  %391 = load i32, ptr %47, align 4, !tbaa !5
  %392 = sext i32 %391 to i64
  %393 = getelementptr inbounds %struct.edge, ptr %63, i64 %392
  %394 = getelementptr inbounds %struct.edge, ptr %393, i32 0, i32 1
  invoke void @_ZNSt5queueIiSt5dequeIiSaIiEEE4pushERKi(ptr noundef nonnull align 8 dereferenceable(80) %42, ptr noundef nonnull align 4 dereferenceable(4) %394)
          to label %395 unwind label %399

395:                                              ; preds = %378
  %396 = load i32, ptr %47, align 4, !tbaa !5
  %397 = sext i32 %396 to i64
  %398 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %14, i64 noundef %397) #8
  store i32 -1, ptr %398, align 4, !tbaa !5
  br label %403

399:                                              ; preds = %378
  %400 = landingpad { ptr, i32 }
          cleanup
  %401 = extractvalue { ptr, i32 } %400, 0
  store ptr %401, ptr %12, align 8
  %402 = extractvalue { ptr, i32 } %400, 1
  store i32 %402, ptr %13, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %47) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %46) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %45) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %44) #8
  br label %412

403:                                              ; preds = %395, %372
  call void @llvm.lifetime.end.p0(i64 4, ptr %47) #8
  br label %404

404:                                              ; preds = %403
  %405 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %45) #8
  br label %353

406:                                              ; preds = %355
  %407 = load i32, ptr %43, align 4, !tbaa !5
  %408 = sext i32 %407 to i64
  %409 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %14, i64 noundef %408) #8
  %410 = load i32, ptr %409, align 4, !tbaa !5
  store i32 %410, ptr %43, align 4, !tbaa !5
  br label %334, !llvm.loop !22

411:                                              ; preds = %334
  call void @llvm.lifetime.end.p0(i64 4, ptr %43) #8
  br label %325, !llvm.loop !23

412:                                              ; preds = %399, %368
  call void @llvm.lifetime.end.p0(i64 4, ptr %43) #8
  br label %422

413:                                              ; preds = %327
  %414 = load i32, ptr %7, align 4, !tbaa !5
  %415 = load i32, ptr %7, align 4, !tbaa !5
  %416 = sext i32 %415 to i64
  %417 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %416) #8
  store i32 %414, ptr %417, align 4, !tbaa !5
  %418 = load i32, ptr %6, align 4, !tbaa !5
  %419 = sext i32 %418 to i64
  invoke void @_ZNSt6vectorIiSaIiEE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %419)
          to label %420 unwind label %364

420:                                              ; preds = %413
  store i1 true, ptr %39, align 1
  store i32 1, ptr %33, align 4
  call void @_ZNSt5queueIiSt5dequeIiSaIiEEED2Ev(ptr noundef nonnull align 8 dereferenceable(80) %42) #8
  call void @llvm.lifetime.end.p0(i64 80, ptr %42) #8
  %421 = load i1, ptr %39, align 1
  br i1 %421, label %425, label %424

422:                                              ; preds = %412, %364
  call void @_ZNSt5queueIiSt5dequeIiSaIiEEED2Ev(ptr noundef nonnull align 8 dereferenceable(80) %42) #8
  br label %423

423:                                              ; preds = %422, %360
  call void @llvm.lifetime.end.p0(i64 80, ptr %42) #8
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %0) #8
  br label %428

424:                                              ; preds = %420
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %0) #8
  br label %425

425:                                              ; preds = %424, %420
  call void @llvm.lifetime.end.p0(i64 4, ptr %30) #8
  call void @_ZN3DSUD2Ev(ptr noundef nonnull align 8 dereferenceable(24) %29) #8
  call void @llvm.lifetime.end.p0(i64 24, ptr %29) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %28) #8
  %426 = getelementptr inbounds %struct.PQ, ptr %81, i64 %80
  %427 = icmp eq ptr %81, %426
  br i1 %427, label %434, label %430

428:                                              ; preds = %423, %356, %316, %204
  call void @llvm.lifetime.end.p0(i64 4, ptr %30) #8
  call void @_ZN3DSUD2Ev(ptr noundef nonnull align 8 dereferenceable(24) %29) #8
  br label %429

429:                                              ; preds = %428, %200
  call void @llvm.lifetime.end.p0(i64 24, ptr %29) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %28) #8
  br label %437

430:                                              ; preds = %430, %425
  %431 = phi ptr [ %426, %425 ], [ %432, %430 ]
  %432 = getelementptr inbounds %struct.PQ, ptr %431, i64 -1
  call void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40) %432) #8
  %433 = icmp eq ptr %432, %81
  br i1 %433, label %434, label %430

434:                                              ; preds = %430, %425
  %435 = getelementptr inbounds %"class.std::vector", ptr %68, i64 %67
  %436 = icmp eq ptr %68, %435
  br i1 %436, label %449, label %445

437:                                              ; preds = %429, %165, %132
  %438 = getelementptr inbounds %struct.PQ, ptr %81, i64 %80
  %439 = icmp eq ptr %81, %438
  br i1 %439, label %444, label %440

440:                                              ; preds = %440, %437
  %441 = phi ptr [ %438, %437 ], [ %442, %440 ]
  %442 = getelementptr inbounds %struct.PQ, ptr %441, i64 -1
  call void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40) %442) #8
  %443 = icmp eq ptr %442, %81
  br i1 %443, label %444, label %440

444:                                              ; preds = %440, %437
  br label %451

445:                                              ; preds = %445, %434
  %446 = phi ptr [ %435, %434 ], [ %447, %445 ]
  %447 = getelementptr inbounds %"class.std::vector", ptr %446, i64 -1
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %447) #8
  %448 = icmp eq ptr %447, %68
  br i1 %448, label %449, label %445

449:                                              ; preds = %445, %434
  %450 = load ptr, ptr %17, align 8
  call void @llvm.stackrestore.p0(ptr %450)
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %14) #8
  call void @llvm.lifetime.end.p0(i64 24, ptr %14) #8
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %9) #8
  call void @llvm.lifetime.end.p0(i64 24, ptr %9) #8
  ret void

451:                                              ; preds = %444, %118
  %452 = getelementptr inbounds %"class.std::vector", ptr %68, i64 %67
  %453 = icmp eq ptr %68, %452
  br i1 %453, label %458, label %454

454:                                              ; preds = %454, %451
  %455 = phi ptr [ %452, %451 ], [ %456, %454 ]
  %456 = getelementptr inbounds %"class.std::vector", ptr %455, i64 -1
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %456) #8
  %457 = icmp eq ptr %456, %68
  br i1 %457, label %458, label %454

458:                                              ; preds = %454, %451
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %14) #8
  br label %459

459:                                              ; preds = %458, %105
  call void @llvm.lifetime.end.p0(i64 24, ptr %14) #8
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %9) #8
  br label %460

460:                                              ; preds = %459, %101
  call void @llvm.lifetime.end.p0(i64 24, ptr %9) #8
  br label %461

461:                                              ; preds = %460
  %462 = load ptr, ptr %12, align 8
  %463 = load i32, ptr %13, align 4
  %464 = insertvalue { ptr, i32 } poison, ptr %462, 0
  %465 = insertvalue { ptr, i32 } %464, i32 %463, 1
  resume { ptr, i32 } %465

466:                                              ; preds = %312
  unreachable
}

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef, ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #0 align 2

declare i32 @__gxx_personality_v0(...)

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: nocallback nofree nosync nounwind willreturn
declare ptr @llvm.stacksave.p0() #3

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(24)) unnamed_addr #2 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare dso_local void @_ZN2PQI4edgeEC2Ev(ptr noundef nonnull align 8 dereferenceable(40)) unnamed_addr #4 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40)) unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNKSt6vectorI4edgeSaIS0_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24)) #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNKSt6vectorI4edgeSaIS0_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24)) #2 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef zeroext i1 @_ZN9__gnu_cxxneIPK4edgeSt6vectorIS1_SaIS1_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) #5

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(16) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8)) #2 align 2

; Function Attrs: nocallback nofree nounwind willreturn memory(argmem: readwrite)
declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg) #6

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZN2PQI4edgeE4pushES0_(ptr noundef nonnull align 8 dereferenceable(40), i64, i64) #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8)) #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZN3DSUC2Ei(ptr noundef nonnull align 8 dereferenceable(24), i32 noundef) unnamed_addr #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_ZN2PQI4edgeE4sizeEv(ptr noundef nonnull align 8 dereferenceable(40)) #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local { i64, i64 } @_ZN2PQI4edgeE3popEv(ptr noundef nonnull align 8 dereferenceable(40)) #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_ZN3DSU4rootEi(ptr noundef nonnull align 8 dereferenceable(24), i32 noundef) #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN2PQI4edgeE3addEx(ptr noundef nonnull align 8 dereferenceable(40), i64 noundef) #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZN2PQI4edgeE5mergeEOS1_(ptr noundef nonnull align 8 dereferenceable(40), ptr noundef nonnull align 8 dereferenceable(40)) #0 align 2

; Function Attrs: noreturn nounwind
declare void @__assert_fail(ptr noundef, ptr noundef, i32 noundef, ptr noundef) #7

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEE9push_backERKi(ptr noundef nonnull align 8 dereferenceable(24), ptr noundef nonnull align 4 dereferenceable(4)) #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorIiSaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(24)) #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorIiSaIiEE3endEv(ptr noundef nonnull align 8 dereferenceable(24)) #2 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) #5

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEdeEv(ptr noundef nonnull align 8 dereferenceable(8)) #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN3DSU7set_parEii(ptr noundef nonnull align 8 dereferenceable(24), i32 noundef, i32 noundef) #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEppEv(ptr noundef nonnull align 8 dereferenceable(8)) #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEEC2IS2_vEEv(ptr noundef nonnull align 8 dereferenceable(80)) unnamed_addr #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEE4pushERKi(ptr noundef nonnull align 8 dereferenceable(80), ptr noundef nonnull align 4 dereferenceable(4)) #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef i64 @_ZNKSt5queueIiSt5dequeIiSaIiEEE4sizeEv(ptr noundef nonnull align 8 dereferenceable(80)) #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt5queueIiSt5dequeIiSaIiEEE5frontEv(ptr noundef nonnull align 8 dereferenceable(80)) #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEE3popEv(ptr noundef nonnull align 8 dereferenceable(80)) #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) #0 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEED2Ev(ptr noundef nonnull align 8 dereferenceable(80)) unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24)) unnamed_addr #2 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local void @_ZN3DSUD2Ev(ptr noundef nonnull align 8 dereferenceable(24)) unnamed_addr #5 align 2

; Function Attrs: nocallback nofree nosync nounwind willreturn
declare void @llvm.stackrestore.p0(ptr) #3

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #2 align 2

attributes #0 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { nocallback nofree nosync nounwind willreturn }
attributes #4 = { inlinehint mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #5 = { inlinehint mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #6 = { nocallback nofree nounwind willreturn memory(argmem: readwrite) }
attributes #7 = { noreturn nounwind "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #8 = { nounwind }
attributes #9 = { noreturn nounwind }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = !{!10, !10, i64 0}
!10 = !{!"any pointer", !7, i64 0}
!11 = !{i64 0, i64 4, !5, i64 4, i64 4, !5, i64 8, i64 8, !12}
!12 = !{!13, !13, i64 0}
!13 = !{!"long long", !7, i64 0}
!14 = !{!15, !6, i64 4}
!15 = !{!"_ZTS4edge", !6, i64 0, !6, i64 4, !13, i64 8}
!16 = !{!15, !6, i64 0}
!17 = !{!15, !13, i64 8}
!18 = distinct !{!18, !19}
!19 = !{!"llvm.loop.mustprogress"}
!20 = distinct !{!20, !19}
!21 = distinct !{!21, !19}
!22 = distinct !{!22, !19}
!23 = distinct !{!23, !19}


; Optimized IR (opt -passes='default<O3>'):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%"class.std::vector" = type { %"struct.std::_Vector_base" }
%"struct.std::_Vector_base" = type { %"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl" }
%"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl" = type { %"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl_data" }
%"struct.std::_Vector_base<int, std::allocator<int>>::_Vector_impl_data" = type { ptr, ptr, ptr }
%"class.std::allocator" = type { i8 }
%"class.__gnu_cxx::__normal_iterator" = type { ptr }
%struct.DSU = type { %"class.std::vector" }
%"class.__gnu_cxx::__normal_iterator.5" = type { ptr }
%"class.std::queue" = type { %"class.std::deque" }
%"class.std::deque" = type { %"class.std::_Deque_base" }
%"class.std::_Deque_base" = type { %"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl" }
%"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl" = type { %"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl_data" }
%"struct.std::_Deque_base<int, std::allocator<int>>::_Deque_impl_data" = type { ptr, i64, %"struct.std::_Deque_iterator", %"struct.std::_Deque_iterator" }
%"struct.std::_Deque_iterator" = type { ptr, ptr, ptr, ptr }
%struct.edge = type { i32, i32, i64 }
%struct.PQ = type { i64, %"class.std::priority_queue" }
%"class.std::priority_queue" = type <{ %"class.std::vector.0", [8 x i8] }>
%"class.std::vector.0" = type { %"struct.std::_Vector_base.1" }
%"struct.std::_Vector_base.1" = type { %"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl" }
%"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl" = type { %"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl_data" }
%"struct.std::_Vector_base<edge, std::allocator<edge>>::_Vector_impl_data" = type { ptr, ptr, ptr }

@.str = external hidden unnamed_addr constant [11 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [92 x i8], align 1
@__PRETTY_FUNCTION__._Z4DMSTiiRKSt6vectorI4edgeSaIS0_EE = external hidden unnamed_addr constant [49 x i8], align 1

; Function Attrs: mustprogress uwtable
define dso_local void @_Z4DMSTiiRKSt6vectorI4edgeSaIS0_EE(ptr dead_on_unwind noalias writable sret(%"class.std::vector") align 8 %0, i32 noundef %1, i32 noundef %2, ptr noundef nonnull align 8 dereferenceable(24) %3) local_unnamed_addr #0 personality ptr @__gxx_personality_v0 {
  %5 = alloca i32, align 4
  %6 = alloca %"class.std::vector", align 8
  %7 = alloca i32, align 4
  %8 = alloca %"class.std::allocator", align 1
  %9 = alloca %"class.std::vector", align 8
  %10 = alloca i32, align 4
  %11 = alloca %"class.std::allocator", align 1
  %12 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %13 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %14 = alloca %struct.DSU, align 8
  %15 = alloca i32, align 4
  %16 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  %17 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  %18 = alloca i32, align 4
  %19 = alloca %"class.std::allocator", align 1
  %20 = alloca %"class.std::queue", align 8
  %21 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  %22 = alloca %"class.__gnu_cxx::__normal_iterator.5", align 8
  store i32 %2, ptr %5, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 24, ptr nonnull %6) #8
  %23 = shl nsw i32 %1, 1
  %24 = add nsw i32 %23, -1
  %25 = sext i32 %24 to i64
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %7) #8
  store i32 -1, ptr %7, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 1, ptr nonnull %8) #8
  call void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1) %8) #8
  invoke void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24) %6, i64 noundef %25, ptr noundef nonnull align 4 dereferenceable(4) %7, ptr noundef nonnull align 1 dereferenceable(1) %8)
          to label %26 unwind label %49

26:                                               ; preds = %4
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %8) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr nonnull %8) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %7) #8
  call void @llvm.lifetime.start.p0(i64 24, ptr nonnull %9) #8
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %10) #8
  store i32 -1, ptr %10, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 1, ptr nonnull %11) #8
  call void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1) %11) #8
  invoke void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %25, ptr noundef nonnull align 4 dereferenceable(4) %10, ptr noundef nonnull align 1 dereferenceable(1) %11)
          to label %27 unwind label %51

27:                                               ; preds = %26
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %11) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr nonnull %11) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %10) #8
  %28 = zext i32 %24 to i64
  %29 = call ptr @llvm.stacksave.p0()
  %30 = alloca %struct.edge, i64 %28, align 16
  %31 = alloca %"class.std::vector", i64 %28, align 16
  %32 = getelementptr inbounds %"class.std::vector", ptr %31, i64 %28
  br label %33

33:                                               ; preds = %33, %27
  %34 = phi ptr [ %31, %27 ], [ %35, %33 ]
  call void @_ZNSt6vectorIiSaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(24) %34) #8
  %35 = getelementptr inbounds i8, ptr %34, i64 24
  %36 = icmp eq ptr %35, %32
  br i1 %36, label %37, label %33

37:                                               ; preds = %33
  %38 = alloca %struct.PQ, i64 %28, align 16
  %39 = getelementptr inbounds %struct.PQ, ptr %38, i64 %28
  br label %40

40:                                               ; preds = %42, %37
  %41 = phi ptr [ %38, %37 ], [ %43, %42 ]
  invoke void @_ZN2PQI4edgeEC2Ev(ptr noundef nonnull align 8 dereferenceable(40) %41)
          to label %42 unwind label %53

42:                                               ; preds = %40
  %43 = getelementptr inbounds i8, ptr %41, i64 40
  %44 = icmp eq ptr %43, %39
  br i1 %44, label %45, label %40

45:                                               ; preds = %42
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %12) #8
  %46 = call ptr @_ZNKSt6vectorI4edgeSaIS0_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %3) #8
  store ptr %46, ptr %12, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %13) #8
  %47 = call ptr @_ZNKSt6vectorI4edgeSaIS0_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %3) #8
  store ptr %47, ptr %13, align 8
  %48 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPK4edgeSt6vectorIS1_SaIS1_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8) %12, ptr noundef nonnull align 8 dereferenceable(8) %13) #8
  br i1 %48, label %.lr.ph, label %._crit_edge

._crit_edge:                                      ; preds = %62, %45
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %13) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %12) #8
  %smax = call i32 @llvm.smax.i32(i32 %1, i32 0)
  %wide.trip.count = zext nneg i32 %smax to i64
  br label %67

49:                                               ; preds = %4
  %50 = landingpad { ptr, i32 }
          cleanup
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %8) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr nonnull %8) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %7) #8
  br label %218

51:                                               ; preds = %26
  %52 = landingpad { ptr, i32 }
          cleanup
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %11) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr nonnull %11) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %10) #8
  br label %217

53:                                               ; preds = %40
  %54 = landingpad { ptr, i32 }
          cleanup
  %55 = icmp eq ptr %38, %41
  br i1 %55, label %.loopexit, label %.preheader107

.preheader107:                                    ; preds = %53, %.preheader107
  %56 = phi ptr [ %57, %.preheader107 ], [ %41, %53 ]
  %57 = getelementptr inbounds i8, ptr %56, i64 -40
  call void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40) %57) #8
  %58 = icmp eq ptr %57, %38
  br i1 %58, label %.loopexit, label %.preheader107

.lr.ph:                                           ; preds = %45, %62
  %59 = call noundef nonnull align 8 dereferenceable(16) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %12) #8
  %.sroa.039.0.copyload = load i64, ptr %59, align 8
  %.sroa.640.0..sroa_idx = getelementptr inbounds i8, ptr %59, i64 8
  %.sroa.640.0.copyload = load i64, ptr %.sroa.640.0..sroa_idx, align 8, !tbaa !9
  %60 = ashr i64 %.sroa.039.0.copyload, 32
  %61 = getelementptr inbounds %struct.PQ, ptr %38, i64 %60
  invoke void @_ZN2PQI4edgeE4pushES0_(ptr noundef nonnull align 8 dereferenceable(40) %61, i64 %.sroa.039.0.copyload, i64 %.sroa.640.0.copyload)
          to label %62 unwind label %65

62:                                               ; preds = %.lr.ph
  %63 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %12) #8
  %64 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPK4edgeSt6vectorIS1_SaIS1_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8) %12, ptr noundef nonnull align 8 dereferenceable(8) %13) #8
  br i1 %64, label %.lr.ph, label %._crit_edge

65:                                               ; preds = %.lr.ph
  %66 = landingpad { ptr, i32 }
          cleanup
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %13) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %12) #8
  br label %203

67:                                               ; preds = %69, %._crit_edge
  %indvars.iv = phi i64 [ %indvars.iv.next, %69 ], [ 0, %._crit_edge ]
  %exitcond.not = icmp eq i64 %indvars.iv, %wide.trip.count
  br i1 %exitcond.not, label %68, label %69

68:                                               ; preds = %67
  call void @llvm.lifetime.start.p0(i64 24, ptr nonnull %14) #8
  invoke void @_ZN3DSUC2Ei(ptr noundef nonnull align 8 dereferenceable(24) %14, i32 noundef %24)
          to label %.preheader106.outer.outer unwind label %85

69:                                               ; preds = %67
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %70 = trunc nuw i64 %indvars.iv.next to i32
  %71 = srem i32 %70, %1
  %72 = zext nneg i32 %71 to i64
  %73 = getelementptr inbounds %struct.PQ, ptr %38, i64 %72
  %.sroa.2.0.insert.shift = shl nuw nsw i64 %72, 32
  %.sroa.0.0.insert.insert = or disjoint i64 %.sroa.2.0.insert.shift, %indvars.iv
  invoke void @_ZN2PQI4edgeE4pushES0_(ptr noundef nonnull align 8 dereferenceable(40) %73, i64 %.sroa.0.0.insert.insert, i64 1000000000000000000)
          to label %67 unwind label %74, !llvm.loop !11

74:                                               ; preds = %69
  %75 = landingpad { ptr, i32 }
          cleanup
  br label %203

.preheader106:                                    ; preds = %.preheader106.outer, %83
  %76 = invoke noundef i32 @_ZN2PQI4edgeE4sizeEv(ptr noundef nonnull align 8 dereferenceable(40) %137)
          to label %77 unwind label %87

77:                                               ; preds = %.preheader106
  %.not = icmp eq i32 %76, 0
  br i1 %.not, label %144, label %78

78:                                               ; preds = %77
  %79 = invoke { i64, i64 } @_ZN2PQI4edgeE3popEv(ptr noundef nonnull align 8 dereferenceable(40) %137)
          to label %80 unwind label %89

80:                                               ; preds = %78
  %81 = extractvalue { i64, i64 } %79, 0
  %.sroa.0.sroa.0.0.extract.trunc = trunc i64 %81 to i32
  %82 = invoke noundef i32 @_ZN3DSU4rootEi(ptr noundef nonnull align 8 dereferenceable(24) %14, i32 noundef %.sroa.0.sroa.0.0.extract.trunc)
          to label %83 unwind label %91

83:                                               ; preds = %80
  %84 = icmp eq i32 %82, %.074.ph
  br i1 %84, label %.preheader106, label %93, !llvm.loop !13

85:                                               ; preds = %68
  %86 = landingpad { ptr, i32 }
          cleanup
  br label %198

87:                                               ; preds = %.preheader106
  %88 = landingpad { ptr, i32 }
          cleanup
  br label %197

89:                                               ; preds = %78
  %90 = landingpad { ptr, i32 }
          cleanup
  br label %197

91:                                               ; preds = %80
  %92 = landingpad { ptr, i32 }
          cleanup
  br label %197

93:                                               ; preds = %83
  %94 = extractvalue { i64, i64 } %79, 1
  %95 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %6, i64 noundef %136) #8
  store i32 %82, ptr %95, align 4, !tbaa !5
  %96 = getelementptr inbounds %struct.edge, ptr %30, i64 %136
  store i64 %81, ptr %96, align 16
  %.sroa.6.0..sroa_idx = getelementptr inbounds i8, ptr %96, i64 8
  store i64 %94, ptr %.sroa.6.0..sroa_idx, align 8, !tbaa !9
  %97 = sext i32 %82 to i64
  %98 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %6, i64 noundef %97) #8
  %99 = load i32, ptr %98, align 4, !tbaa !5
  %100 = icmp eq i32 %99, -1
  br i1 %100, label %.preheader106.outer, label %101

101:                                              ; preds = %93
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %15) #8
  store i32 %82, ptr %15, align 4, !tbaa !5
  %102 = sext i32 %.071.ph.ph to i64
  %103 = getelementptr inbounds %struct.PQ, ptr %38, i64 %102
  %104 = getelementptr inbounds %"class.std::vector", ptr %31, i64 %102
  br label %105

105:                                              ; preds = %130, %101
  %106 = phi i32 [ %129, %130 ], [ %82, %101 ]
  %107 = sext i32 %106 to i64
  %108 = getelementptr inbounds %struct.PQ, ptr %38, i64 %107
  %109 = getelementptr inbounds %struct.edge, ptr %30, i64 %107, i32 2
  %110 = load i64, ptr %109, align 8, !tbaa !14
  %111 = sub nsw i64 0, %110
  call void @_ZN2PQI4edgeE3addEx(ptr noundef nonnull align 8 dereferenceable(40) %108, i64 noundef %111)
  %112 = load i32, ptr %15, align 4, !tbaa !5
  %113 = sext i32 %112 to i64
  %114 = getelementptr inbounds %struct.PQ, ptr %38, i64 %113
  invoke void @_ZN2PQI4edgeE5mergeEOS1_(ptr noundef nonnull align 8 dereferenceable(40) %103, ptr noundef nonnull align 8 dereferenceable(40) %114)
          to label %115 unwind label %121

115:                                              ; preds = %105
  %116 = load i32, ptr %15, align 4, !tbaa !5
  %117 = sext i32 %116 to i64
  %118 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %6, i64 noundef %117) #8
  %119 = load i32, ptr %118, align 4, !tbaa !5
  %.not92 = icmp eq i32 %119, -1
  br i1 %.not92, label %120, label %123

120:                                              ; preds = %115
  call void @__assert_fail(ptr noundef nonnull @.str, ptr noundef nonnull @.str.1, i32 noundef 63, ptr noundef nonnull @__PRETTY_FUNCTION__._Z4DMSTiiRKSt6vectorI4edgeSaIS0_EE) #9
  unreachable

121:                                              ; preds = %124, %123, %105
  %122 = landingpad { ptr, i32 }
          cleanup
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %15) #8
  br label %197

123:                                              ; preds = %115
  invoke void @_ZNSt6vectorIiSaIiEE9push_backERKi(ptr noundef nonnull align 8 dereferenceable(24) %104, ptr noundef nonnull align 4 dereferenceable(4) %15)
          to label %124 unwind label %121

124:                                              ; preds = %123
  %125 = load i32, ptr %15, align 4, !tbaa !5
  %126 = sext i32 %125 to i64
  %127 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %6, i64 noundef %126) #8
  %128 = load i32, ptr %127, align 4, !tbaa !5
  %129 = invoke noundef i32 @_ZN3DSU4rootEi(ptr noundef nonnull align 8 dereferenceable(24) %14, i32 noundef %128)
          to label %130 unwind label %121

130:                                              ; preds = %124
  store i32 %129, ptr %15, align 4, !tbaa !5
  %.not98 = icmp eq i32 %129, %82
  br i1 %.not98, label %131, label %105, !llvm.loop !16

131:                                              ; preds = %130
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %16) #8
  %132 = call ptr @_ZNSt6vectorIiSaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %104) #8
  store ptr %132, ptr %16, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %17) #8
  %133 = call ptr @_ZNSt6vectorIiSaIiEE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %104) #8
  store ptr %133, ptr %17, align 8
  %134 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8) %16, ptr noundef nonnull align 8 dereferenceable(8) %17) #8
  br i1 %134, label %.lr.ph112, label %._crit_edge113

._crit_edge113:                                   ; preds = %.lr.ph112, %131
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %17) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %16) #8
  %135 = add nsw i32 %.071.ph.ph, 1
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %15) #8
  br label %.preheader106.outer.outer

.preheader106.outer.outer:                        ; preds = %68, %._crit_edge113
  %.074.ph.ph = phi i32 [ %.071.ph.ph, %._crit_edge113 ], [ 0, %68 ]
  %.071.ph.ph = phi i32 [ %135, %._crit_edge113 ], [ %1, %68 ]
  br label %.preheader106.outer

.preheader106.outer:                              ; preds = %.preheader106.outer.outer, %93
  %.074.ph = phi i32 [ %82, %93 ], [ %.074.ph.ph, %.preheader106.outer.outer ]
  %136 = sext i32 %.074.ph to i64
  %137 = getelementptr inbounds %struct.PQ, ptr %38, i64 %136
  br label %.preheader106

.lr.ph112:                                        ; preds = %131, %.lr.ph112
  %138 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %16) #8
  %139 = load i32, ptr %138, align 4, !tbaa !5
  %140 = sext i32 %139 to i64
  %141 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %140) #8
  store i32 %.071.ph.ph, ptr %141, align 4, !tbaa !5
  call void @_ZN3DSU7set_parEii(ptr noundef nonnull align 8 dereferenceable(24) %14, i32 noundef %139, i32 noundef %.071.ph.ph)
  %142 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %16) #8
  %143 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8) %16, ptr noundef nonnull align 8 dereferenceable(8) %17) #8
  br i1 %143, label %.lr.ph112, label %._crit_edge113

144:                                              ; preds = %77
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %18) #8
  store i32 -1, ptr %18, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 1, ptr nonnull %19) #8
  call void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1) %19) #8
  invoke void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %25, ptr noundef nonnull align 4 dereferenceable(4) %18, ptr noundef nonnull align 1 dereferenceable(1) %19)
          to label %145 unwind label %167

145:                                              ; preds = %144
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %19) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr nonnull %19) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %18) #8
  call void @llvm.lifetime.start.p0(i64 80, ptr nonnull %20) #8
  invoke void @_ZNSt5queueIiSt5dequeIiSaIiEEEC2IS2_vEEv(ptr noundef nonnull align 8 dereferenceable(80) %20)
          to label %146 unwind label %169

146:                                              ; preds = %145
  invoke void @_ZNSt5queueIiSt5dequeIiSaIiEEE4pushERKi(ptr noundef nonnull align 8 dereferenceable(80) %20, ptr noundef nonnull align 4 dereferenceable(4) %5)
          to label %.preheader105 unwind label %171

.preheader105:                                    ; preds = %146
  %147 = call noundef i64 @_ZNKSt5queueIiSt5dequeIiSaIiEEE4sizeEv(ptr noundef nonnull align 8 dereferenceable(80) %20)
  %.not87121 = icmp eq i64 %147, 0
  br i1 %.not87121, label %._crit_edge123, label %.lr.ph122

.loopexit104:                                     ; preds = %._crit_edge116, %.lr.ph122
  %148 = call noundef i64 @_ZNKSt5queueIiSt5dequeIiSaIiEEE4sizeEv(ptr noundef nonnull align 8 dereferenceable(80) %20)
  %.not87 = icmp eq i64 %148, 0
  br i1 %.not87, label %._crit_edge123, label %.lr.ph122, !llvm.loop !17

.lr.ph122:                                        ; preds = %.preheader105, %.loopexit104
  %149 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt5queueIiSt5dequeIiSaIiEEE5frontEv(ptr noundef nonnull align 8 dereferenceable(80) %20)
  %150 = load i32, ptr %149, align 4, !tbaa !5
  call void @_ZNSt5queueIiSt5dequeIiSaIiEEE3popEv(ptr noundef nonnull align 8 dereferenceable(80) %20)
  %151 = sext i32 %150 to i64
  %152 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %151) #8
  %153 = load i32, ptr %152, align 4, !tbaa !5
  %.not88117 = icmp eq i32 %153, -1
  br i1 %.not88117, label %.loopexit104, label %.lr.ph120

.lr.ph120:                                        ; preds = %.lr.ph122, %._crit_edge116
  %154 = phi i64 [ %164, %._crit_edge116 ], [ %151, %.lr.ph122 ]
  %.069118 = phi i32 [ %163, %._crit_edge116 ], [ %150, %.lr.ph122 ]
  %155 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %154) #8
  %156 = load i32, ptr %155, align 4, !tbaa !5
  %157 = sext i32 %156 to i64
  %158 = getelementptr inbounds %"class.std::vector", ptr %31, i64 %157
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %21) #8
  %159 = call ptr @_ZNSt6vectorIiSaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %158) #8
  store ptr %159, ptr %21, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %22) #8
  %160 = call ptr @_ZNSt6vectorIiSaIiEE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %158) #8
  store ptr %160, ptr %22, align 8
  %161 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8) %21, ptr noundef nonnull align 8 dereferenceable(8) %22) #8
  br i1 %161, label %.lr.ph115, label %._crit_edge116

._crit_edge116:                                   ; preds = %187, %.lr.ph120
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %22) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %21) #8
  %162 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %154) #8
  %163 = load i32, ptr %162, align 4, !tbaa !5
  %164 = sext i32 %163 to i64
  %165 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %164) #8
  %166 = load i32, ptr %165, align 4, !tbaa !5
  %.not88 = icmp eq i32 %166, -1
  br i1 %.not88, label %.loopexit104, label %.lr.ph120, !llvm.loop !18

167:                                              ; preds = %144
  %168 = landingpad { ptr, i32 }
          cleanup
  call void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1) %19) #8
  call void @llvm.lifetime.end.p0(i64 1, ptr nonnull %19) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %18) #8
  br label %197

169:                                              ; preds = %145
  %170 = landingpad { ptr, i32 }
          cleanup
  br label %196

171:                                              ; preds = %._crit_edge123, %146
  %172 = landingpad { ptr, i32 }
          cleanup
  br label %195

.lr.ph115:                                        ; preds = %.lr.ph120, %187
  %173 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %21) #8
  %174 = load i32, ptr %173, align 4, !tbaa !5
  %.not89 = icmp eq i32 %174, %.069118
  br i1 %.not89, label %187, label %175

175:                                              ; preds = %.lr.ph115
  %176 = sext i32 %174 to i64
  %177 = getelementptr inbounds %struct.edge, ptr %30, i64 %176
  %178 = load i32, ptr %177, align 16, !tbaa !19
  %179 = getelementptr inbounds i8, ptr %177, i64 4
  %180 = load i32, ptr %179, align 4, !tbaa !20
  %181 = sext i32 %180 to i64
  %182 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %181) #8
  store i32 %178, ptr %182, align 4, !tbaa !5
  invoke void @_ZNSt5queueIiSt5dequeIiSaIiEEE4pushERKi(ptr noundef nonnull align 8 dereferenceable(80) %20, ptr noundef nonnull align 4 dereferenceable(4) %179)
          to label %183 unwind label %185

183:                                              ; preds = %175
  %184 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %9, i64 noundef %176) #8
  store i32 -1, ptr %184, align 4, !tbaa !5
  br label %187

185:                                              ; preds = %175
  %186 = landingpad { ptr, i32 }
          cleanup
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %22) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %21) #8
  br label %195

187:                                              ; preds = %183, %.lr.ph115
  %188 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %21) #8
  %189 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8) %21, ptr noundef nonnull align 8 dereferenceable(8) %22) #8
  br i1 %189, label %.lr.ph115, label %._crit_edge116

._crit_edge123:                                   ; preds = %.loopexit104, %.preheader105
  %190 = load i32, ptr %5, align 4, !tbaa !5
  %191 = sext i32 %190 to i64
  %192 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %191) #8
  store i32 %190, ptr %192, align 4, !tbaa !5
  %193 = sext i32 %1 to i64
  invoke void @_ZNSt6vectorIiSaIiEE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24) %0, i64 noundef %193)
          to label %194 unwind label %171

194:                                              ; preds = %._crit_edge123
  call void @_ZNSt5queueIiSt5dequeIiSaIiEEED2Ev(ptr noundef nonnull align 8 dereferenceable(80) %20) #8
  call void @llvm.lifetime.end.p0(i64 80, ptr nonnull %20) #8
  call void @_ZN3DSUD2Ev(ptr noundef nonnull align 8 dereferenceable(24) %14) #8
  call void @llvm.lifetime.end.p0(i64 24, ptr nonnull %14) #8
  br label %199

195:                                              ; preds = %185, %171
  %.pn = phi { ptr, i32 } [ %186, %185 ], [ %172, %171 ]
  call void @_ZNSt5queueIiSt5dequeIiSaIiEEED2Ev(ptr noundef nonnull align 8 dereferenceable(80) %20) #8
  br label %196

196:                                              ; preds = %195, %169
  %.pn.pn = phi { ptr, i32 } [ %.pn, %195 ], [ %170, %169 ]
  call void @llvm.lifetime.end.p0(i64 80, ptr nonnull %20) #8
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %0) #8
  br label %197

197:                                              ; preds = %89, %121, %91, %196, %167, %87
  %.pn93.pn.pn = phi { ptr, i32 } [ %.pn.pn, %196 ], [ %168, %167 ], [ %88, %87 ], [ %90, %89 ], [ %122, %121 ], [ %92, %91 ]
  call void @_ZN3DSUD2Ev(ptr noundef nonnull align 8 dereferenceable(24) %14) #8
  br label %198

198:                                              ; preds = %197, %85
  %.pn93.pn.pn.pn = phi { ptr, i32 } [ %.pn93.pn.pn, %197 ], [ %86, %85 ]
  call void @llvm.lifetime.end.p0(i64 24, ptr nonnull %14) #8
  br label %203

199:                                              ; preds = %194, %199
  %200 = phi ptr [ %39, %194 ], [ %201, %199 ]
  %201 = getelementptr inbounds i8, ptr %200, i64 -40
  call void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40) %201) #8
  %202 = icmp eq ptr %201, %38
  br i1 %202, label %.preheader, label %199

203:                                              ; preds = %198, %74, %65
  %.pn99 = phi { ptr, i32 } [ %66, %65 ], [ %75, %74 ], [ %.pn93.pn.pn.pn, %198 ]
  br label %204

204:                                              ; preds = %203, %204
  %205 = phi ptr [ %39, %203 ], [ %206, %204 ]
  %206 = getelementptr inbounds i8, ptr %205, i64 -40
  call void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40) %206) #8
  %207 = icmp eq ptr %206, %38
  br i1 %207, label %.loopexit, label %204

.preheader:                                       ; preds = %199, %.preheader
  %208 = phi ptr [ %209, %.preheader ], [ %32, %199 ]
  %209 = getelementptr inbounds i8, ptr %208, i64 -24
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %209) #8
  %210 = icmp eq ptr %209, %31
  br i1 %210, label %211, label %.preheader

211:                                              ; preds = %.preheader
  call void @llvm.stackrestore.p0(ptr %29)
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %9) #8
  call void @llvm.lifetime.end.p0(i64 24, ptr nonnull %9) #8
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %6) #8
  call void @llvm.lifetime.end.p0(i64 24, ptr nonnull %6) #8
  ret void

.loopexit:                                        ; preds = %.preheader107, %204, %53
  %.pn99.pn = phi { ptr, i32 } [ %54, %53 ], [ %.pn99, %204 ], [ %54, %.preheader107 ]
  br label %212

212:                                              ; preds = %.loopexit, %212
  %213 = phi ptr [ %32, %.loopexit ], [ %214, %212 ]
  %214 = getelementptr inbounds i8, ptr %213, i64 -24
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %214) #8
  %215 = icmp eq ptr %214, %31
  br i1 %215, label %216, label %212

216:                                              ; preds = %212
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %9) #8
  br label %217

217:                                              ; preds = %216, %51
  %.pn99.pn.pn = phi { ptr, i32 } [ %.pn99.pn, %216 ], [ %52, %51 ]
  call void @llvm.lifetime.end.p0(i64 24, ptr nonnull %9) #8
  call void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24) %6) #8
  br label %218

218:                                              ; preds = %217, %49
  %.pn99.pn.pn.pn = phi { ptr, i32 } [ %.pn99.pn.pn, %217 ], [ %50, %49 ]
  call void @llvm.lifetime.end.p0(i64 24, ptr nonnull %6) #8
  resume { ptr, i32 } %.pn99.pn.pn.pn
}

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSaIiEC2Ev(ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEEC2EmRKiRKS0_(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef, ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #0 align 2

declare i32 @__gxx_personality_v0(...)

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn
declare ptr @llvm.stacksave.p0() #3

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(24)) unnamed_addr #2 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare dso_local void @_ZN2PQI4edgeEC2Ev(ptr noundef nonnull align 8 dereferenceable(40)) unnamed_addr #4 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local void @_ZN2PQI4edgeED2Ev(ptr noundef nonnull align 8 dereferenceable(40)) unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNKSt6vectorI4edgeSaIS0_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNKSt6vectorI4edgeSaIS0_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24)) local_unnamed_addr #2 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef zeroext i1 @_ZN9__gnu_cxxneIPK4edgeSt6vectorIS1_SaIS1_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #5

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(16) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZN2PQI4edgeE4pushES0_(ptr noundef nonnull align 8 dereferenceable(40), i64, i64) local_unnamed_addr #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPK4edgeSt6vectorIS1_SaIS1_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZN3DSUC2Ei(ptr noundef nonnull align 8 dereferenceable(24), i32 noundef) unnamed_addr #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_ZN2PQI4edgeE4sizeEv(ptr noundef nonnull align 8 dereferenceable(40)) local_unnamed_addr #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local { i64, i64 } @_ZN2PQI4edgeE3popEv(ptr noundef nonnull align 8 dereferenceable(40)) local_unnamed_addr #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_ZN3DSU4rootEi(ptr noundef nonnull align 8 dereferenceable(24), i32 noundef) local_unnamed_addr #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt6vectorIiSaIiEEixEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN2PQI4edgeE3addEx(ptr noundef nonnull align 8 dereferenceable(40), i64 noundef) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZN2PQI4edgeE5mergeEOS1_(ptr noundef nonnull align 8 dereferenceable(40), ptr noundef nonnull align 8 dereferenceable(40)) local_unnamed_addr #0 align 2

; Function Attrs: noreturn nounwind
declare void @__assert_fail(ptr noundef, ptr noundef, i32 noundef, ptr noundef) local_unnamed_addr #6

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEE9push_backERKi(ptr noundef nonnull align 8 dereferenceable(24), ptr noundef nonnull align 4 dereferenceable(4)) local_unnamed_addr #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorIiSaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(24)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorIiSaIiEE3endEv(ptr noundef nonnull align 8 dereferenceable(24)) local_unnamed_addr #2 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef zeroext i1 @_ZN9__gnu_cxxneIPiSt6vectorIiSaIiEEEEbRKNS_17__normal_iteratorIT_T0_EESA_(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #5

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEdeEv(ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN3DSU7set_parEii(ptr noundef nonnull align 8 dereferenceable(24), i32 noundef, i32 noundef) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEppEv(ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEEC2IS2_vEEv(ptr noundef nonnull align 8 dereferenceable(80)) unnamed_addr #0 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEE4pushERKi(ptr noundef nonnull align 8 dereferenceable(80), ptr noundef nonnull align 4 dereferenceable(4)) local_unnamed_addr #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef i64 @_ZNKSt5queueIiSt5dequeIiSaIiEEE4sizeEv(ptr noundef nonnull align 8 dereferenceable(80)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZNSt5queueIiSt5dequeIiSaIiEEE5frontEv(ptr noundef nonnull align 8 dereferenceable(80)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEE3popEv(ptr noundef nonnull align 8 dereferenceable(80)) local_unnamed_addr #2 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) local_unnamed_addr #0 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local void @_ZNSt5queueIiSt5dequeIiSaIiEEED2Ev(ptr noundef nonnull align 8 dereferenceable(80)) unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt6vectorIiSaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(24)) unnamed_addr #2 align 2

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local void @_ZN3DSUD2Ev(ptr noundef nonnull align 8 dereferenceable(24)) unnamed_addr #5 align 2

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn
declare void @llvm.stackrestore.p0(ptr) #3

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt15__new_allocatorIiED2Ev(ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #2 align 2

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.smax.i32(i32, i32) #7

attributes #0 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { mustprogress nocallback nofree nosync nounwind willreturn }
attributes #4 = { inlinehint mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #5 = { inlinehint mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #6 = { noreturn nounwind "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #7 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
attributes #8 = { nounwind }
attributes #9 = { noreturn nounwind }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = !{!10, !10, i64 0}
!10 = !{!"long long", !7, i64 0}
!11 = distinct !{!11, !12}
!12 = !{!"llvm.loop.mustprogress"}
!13 = distinct !{!13, !12}
!14 = !{!15, !10, i64 8}
!15 = !{!"_ZTS4edge", !6, i64 0, !6, i64 4, !10, i64 8}
!16 = distinct !{!16, !12}
!17 = distinct !{!17, !12}
!18 = distinct !{!18, !12}
!19 = !{!15, !6, i64 0}
!20 = !{!15, !6, i64 4}


; Effective O3 passes: EarlyCSEPass,GVNPass,GlobalOptPass,IPSCCPPass,IndVarSimplifyPass,InferFunctionAttrsPass,InstCombinePass,InstSimplifyPass,JumpThreadingPass,LCSSAPass,LICMPass,LoopInstSimplifyPass,LoopRotatePass,LoopSimplifyPass,LoopUnrollPass,ReassociatePass,SCCPPass,SROAPass,SimplifyCFGPass