; LLVM IR from tangjz/acm-icpc :: 51nod (1395)

; 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::set" = type { %"class.std::_Rb_tree" }
%"class.std::_Rb_tree" = type { %"struct.std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>>::_Rb_tree_impl" }
%"struct.std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>>::_Rb_tree_impl" = type { [8 x i8], %"struct.std::_Rb_tree_header" }
%"struct.std::_Rb_tree_header" = type { %"struct.std::_Rb_tree_node_base", i64 }
%"struct.std::_Rb_tree_node_base" = type { i32, ptr, ptr, ptr }
%struct.Edge = type { i32, i32 }
%"struct.std::pair" = type <{ %"struct.std::_Rb_tree_const_iterator", i8, [7 x i8] }>
%"struct.std::_Rb_tree_const_iterator" = type { ptr }
%"class.std::reverse_iterator" = type { %"struct.std::_Rb_tree_const_iterator" }

@t = external dso_local global i32, align 4
@n = external dso_local global i32, align 4
@h = external dso_local global [200002 x i32], align 16
@pre = external dso_local global [100001 x i32], align 16
@suf = external dso_local global [100001 x i32], align 16
@tot = external dso_local global i32, align 4
@lnk = external dso_local global [200002 x i32], align 16
@str = external dso_local global [100001 x i8], align 16
@buf = external dso_local global [200002 x i8], align 16
@sp = external dso_local global %"class.std::set", align 8
@e = external dso_local global [200002 x %struct.Edge], align 16
@.str = external hidden unnamed_addr constant [3 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.2 = external hidden unnamed_addr constant [4 x i8], align 1

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

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

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() #1 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  %6 = alloca i32, align 4
  %7 = alloca %"class.std::set", align 8
  %8 = alloca i32, align 4
  %9 = alloca i32, align 4
  %10 = alloca %"struct.std::pair", align 8
  %11 = alloca %struct.Edge, align 4
  %12 = alloca i32, align 4
  %13 = alloca %"struct.std::_Rb_tree_const_iterator", align 8
  %14 = alloca %"class.std::set", align 8
  %15 = alloca i32, align 4
  %16 = alloca %"struct.std::pair", align 8
  %17 = alloca %struct.Edge, align 4
  %18 = alloca i32, align 4
  %19 = alloca %"class.std::reverse_iterator", align 8
  %20 = alloca i32, align 4
  %21 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  %22 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str, ptr noundef @t)
  br label %23

23:                                               ; preds = %406, %0
  %24 = load i32, ptr @t, align 4, !tbaa !5
  %25 = add nsw i32 %24, -1
  store i32 %25, ptr @t, align 4, !tbaa !5
  %26 = icmp ne i32 %24, 0
  br i1 %26, label %27, label %409

27:                                               ; preds = %23
  %28 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str.1, ptr noundef @str)
  %29 = call i64 @strlen(ptr noundef @str) #9
  %30 = trunc i64 %29 to i32
  store i32 %30, ptr @n, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %2) #10
  store i32 0, ptr %2, align 4, !tbaa !5
  br label %31

31:                                               ; preds = %50, %27
  %32 = load i32, ptr %2, align 4, !tbaa !5
  %33 = load i32, ptr @n, align 4, !tbaa !5
  %34 = icmp slt i32 %32, %33
  br i1 %34, label %36, label %35

35:                                               ; preds = %31
  call void @llvm.lifetime.end.p0(i64 4, ptr %2) #10
  br label %53

36:                                               ; preds = %31
  %37 = load i32, ptr %2, align 4, !tbaa !5
  %38 = sext i32 %37 to i64
  %39 = getelementptr inbounds [100001 x i8], ptr @str, i64 0, i64 %38
  %40 = load i8, ptr %39, align 1, !tbaa !9
  %41 = load i32, ptr %2, align 4, !tbaa !5
  %42 = shl i32 %41, 1
  %43 = sext i32 %42 to i64
  %44 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %43
  store i8 %40, ptr %44, align 1, !tbaa !9
  %45 = load i32, ptr %2, align 4, !tbaa !5
  %46 = shl i32 %45, 1
  %47 = or i32 %46, 1
  %48 = sext i32 %47 to i64
  %49 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %48
  store i8 35, ptr %49, align 1, !tbaa !9
  br label %50

50:                                               ; preds = %36
  %51 = load i32, ptr %2, align 4, !tbaa !5
  %52 = add nsw i32 %51, 1
  store i32 %52, ptr %2, align 4, !tbaa !5
  br label %31, !llvm.loop !10

53:                                               ; preds = %35
  %54 = load i32, ptr @n, align 4, !tbaa !5
  %55 = sub nsw i32 %54, 1
  %56 = shl i32 %55, 1
  %57 = or i32 %56, 1
  %58 = sext i32 %57 to i64
  %59 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %58
  store i8 0, ptr %59, align 1, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 4, ptr %3) #10
  store i32 0, ptr %3, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %4) #10
  store i32 0, ptr %4, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %5) #10
  store i32 0, ptr %5, align 4, !tbaa !5
  br label %60

60:                                               ; preds = %145, %53
  %61 = load i32, ptr %3, align 4, !tbaa !5
  %62 = load i32, ptr @n, align 4, !tbaa !5
  %63 = sub nsw i32 %62, 1
  %64 = shl i32 %63, 1
  %65 = icmp sle i32 %61, %64
  br i1 %65, label %67, label %66

66:                                               ; preds = %60
  call void @llvm.lifetime.end.p0(i64 4, ptr %5) #10
  call void @llvm.lifetime.end.p0(i64 4, ptr %4) #10
  call void @llvm.lifetime.end.p0(i64 4, ptr %3) #10
  br label %148

67:                                               ; preds = %60
  %68 = load i32, ptr %3, align 4, !tbaa !5
  %69 = load i32, ptr %4, align 4, !tbaa !5
  %70 = icmp slt i32 %68, %69
  call void @llvm.lifetime.start.p0(i64 4, ptr %6) #10
  br i1 %70, label %71, label %83

71:                                               ; preds = %67
  %72 = load i32, ptr %4, align 4, !tbaa !5
  %73 = load i32, ptr %3, align 4, !tbaa !5
  %74 = sub nsw i32 %72, %73
  store i32 %74, ptr %6, align 4, !tbaa !5
  %75 = load i32, ptr %5, align 4, !tbaa !5
  %76 = shl i32 %75, 1
  %77 = load i32, ptr %3, align 4, !tbaa !5
  %78 = sub nsw i32 %76, %77
  %79 = sext i32 %78 to i64
  %80 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %79
  %81 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4) %6, ptr noundef nonnull align 4 dereferenceable(4) %80)
  %82 = load i32, ptr %81, align 4, !tbaa !5
  br label %84

83:                                               ; preds = %67
  br label %84

84:                                               ; preds = %83, %71
  %85 = phi i32 [ %82, %71 ], [ 0, %83 ]
  %86 = load i32, ptr %3, align 4, !tbaa !5
  %87 = sext i32 %86 to i64
  %88 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %87
  store i32 %85, ptr %88, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %6) #10
  br label %89

89:                                               ; preds = %121, %84
  %90 = load i32, ptr %3, align 4, !tbaa !5
  %91 = sext i32 %90 to i64
  %92 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %91
  %93 = load i32, ptr %92, align 4, !tbaa !5
  %94 = load i32, ptr %3, align 4, !tbaa !5
  %95 = icmp sle i32 %93, %94
  br i1 %95, label %96, label %118

96:                                               ; preds = %89
  %97 = load i32, ptr %3, align 4, !tbaa !5
  %98 = load i32, ptr %3, align 4, !tbaa !5
  %99 = sext i32 %98 to i64
  %100 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %99
  %101 = load i32, ptr %100, align 4, !tbaa !5
  %102 = sub nsw i32 %97, %101
  %103 = sext i32 %102 to i64
  %104 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %103
  %105 = load i8, ptr %104, align 1, !tbaa !9
  %106 = sext i8 %105 to i32
  %107 = load i32, ptr %3, align 4, !tbaa !5
  %108 = load i32, ptr %3, align 4, !tbaa !5
  %109 = sext i32 %108 to i64
  %110 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %109
  %111 = load i32, ptr %110, align 4, !tbaa !5
  %112 = add nsw i32 %107, %111
  %113 = sext i32 %112 to i64
  %114 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %113
  %115 = load i8, ptr %114, align 1, !tbaa !9
  %116 = sext i8 %115 to i32
  %117 = icmp eq i32 %106, %116
  br label %118

118:                                              ; preds = %96, %89
  %119 = phi i1 [ false, %89 ], [ %117, %96 ]
  br i1 %119, label %120, label %127

120:                                              ; preds = %118
  br label %121

121:                                              ; preds = %120
  %122 = load i32, ptr %3, align 4, !tbaa !5
  %123 = sext i32 %122 to i64
  %124 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %123
  %125 = load i32, ptr %124, align 4, !tbaa !5
  %126 = add nsw i32 %125, 1
  store i32 %126, ptr %124, align 4, !tbaa !5
  br label %89, !llvm.loop !12

127:                                              ; preds = %118
  %128 = load i32, ptr %4, align 4, !tbaa !5
  %129 = load i32, ptr %3, align 4, !tbaa !5
  %130 = load i32, ptr %3, align 4, !tbaa !5
  %131 = sext i32 %130 to i64
  %132 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %131
  %133 = load i32, ptr %132, align 4, !tbaa !5
  %134 = add nsw i32 %129, %133
  %135 = icmp slt i32 %128, %134
  br i1 %135, label %136, label %144

136:                                              ; preds = %127
  %137 = load i32, ptr %3, align 4, !tbaa !5
  %138 = load i32, ptr %3, align 4, !tbaa !5
  %139 = sext i32 %138 to i64
  %140 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %139
  %141 = load i32, ptr %140, align 4, !tbaa !5
  %142 = add nsw i32 %137, %141
  store i32 %142, ptr %4, align 4, !tbaa !5
  %143 = load i32, ptr %3, align 4, !tbaa !5
  store i32 %143, ptr %5, align 4, !tbaa !5
  br label %144

144:                                              ; preds = %136, %127
  br label %145

145:                                              ; preds = %144
  %146 = load i32, ptr %3, align 4, !tbaa !5
  %147 = add nsw i32 %146, 1
  store i32 %147, ptr %3, align 4, !tbaa !5
  br label %60, !llvm.loop !13

148:                                              ; preds = %66
  call void @llvm.lifetime.start.p0(i64 48, ptr %7) #10
  call void @llvm.memset.p0.i64(ptr align 8 %7, i8 0, i64 48, i1 false)
  call void @_ZNSt3setIiSt4lessIiESaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(48) %7) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEE4swapERS3_(ptr noundef nonnull align 8 dereferenceable(48) %7, ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(48) %7) #10
  call void @llvm.lifetime.end.p0(i64 48, ptr %7) #10
  store i32 0, ptr @tot, align 4, !tbaa !5
  %149 = load i32, ptr @n, align 4, !tbaa !5
  %150 = shl i32 %149, 1
  %151 = sext i32 %150 to i64
  %152 = mul i64 %151, 4
  call void @llvm.memset.p0.i64(ptr align 16 @lnk, i8 -1, i64 %152, i1 false)
  call void @llvm.lifetime.start.p0(i64 4, ptr %8) #10
  store i32 0, ptr %8, align 4, !tbaa !5
  br label %153

153:                                              ; preds = %257, %148
  %154 = load i32, ptr %8, align 4, !tbaa !5
  %155 = load i32, ptr @n, align 4, !tbaa !5
  %156 = sub nsw i32 %155, 1
  %157 = shl i32 %156, 1
  %158 = icmp sle i32 %154, %157
  br i1 %158, label %160, label %159

159:                                              ; preds = %153
  store i32 13, ptr %9, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %8) #10
  br label %260

160:                                              ; preds = %153
  %161 = call { ptr, i8 } @_ZNSt3setIiSt4lessIiESaIiEE6insertERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %8)
  %162 = getelementptr inbounds { ptr, i8 }, ptr %10, i32 0, i32 0
  %163 = extractvalue { ptr, i8 } %161, 0
  store ptr %163, ptr %162, align 8
  %164 = getelementptr inbounds { ptr, i8 }, ptr %10, i32 0, i32 1
  %165 = extractvalue { ptr, i8 } %161, 1
  store i8 %165, ptr %164, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr %11) #10
  %166 = getelementptr inbounds %struct.Edge, ptr %11, i32 0, i32 0
  %167 = load i32, ptr %8, align 4, !tbaa !5
  %168 = load i32, ptr %8, align 4, !tbaa !5
  %169 = sext i32 %168 to i64
  %170 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %169
  %171 = load i32, ptr %170, align 4, !tbaa !5
  %172 = add nsw i32 %167, %171
  %173 = sext i32 %172 to i64
  %174 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %173
  %175 = load i32, ptr %174, align 4, !tbaa !5
  store i32 %175, ptr %166, align 4, !tbaa !14
  %176 = getelementptr inbounds %struct.Edge, ptr %11, i32 0, i32 1
  %177 = load i32, ptr %8, align 4, !tbaa !5
  store i32 %177, ptr %176, align 4, !tbaa !16
  %178 = load i32, ptr @tot, align 4, !tbaa !5
  %179 = sext i32 %178 to i64
  %180 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %179
  call void @llvm.memcpy.p0.p0.i64(ptr align 8 %180, ptr align 4 %11, i64 8, i1 false), !tbaa.struct !17
  call void @llvm.lifetime.end.p0(i64 8, ptr %11) #10
  %181 = load i32, ptr @tot, align 4, !tbaa !5
  %182 = add nsw i32 %181, 1
  store i32 %182, ptr @tot, align 4, !tbaa !5
  %183 = load i32, ptr %8, align 4, !tbaa !5
  %184 = load i32, ptr %8, align 4, !tbaa !5
  %185 = sext i32 %184 to i64
  %186 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %185
  %187 = load i32, ptr %186, align 4, !tbaa !5
  %188 = add nsw i32 %183, %187
  %189 = sext i32 %188 to i64
  %190 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %189
  store i32 %181, ptr %190, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %12) #10
  %191 = load i32, ptr %8, align 4, !tbaa !5
  %192 = sext i32 %191 to i64
  %193 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %192
  %194 = load i32, ptr %193, align 4, !tbaa !5
  store i32 %194, ptr %12, align 4, !tbaa !5
  br label %195

195:                                              ; preds = %205, %160
  %196 = load i32, ptr %12, align 4, !tbaa !5
  %197 = icmp ne i32 %196, -1
  br i1 %197, label %199, label %198

198:                                              ; preds = %195
  store i32 16, ptr %9, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %12) #10
  br label %211

199:                                              ; preds = %195
  %200 = load i32, ptr %12, align 4, !tbaa !5
  %201 = sext i32 %200 to i64
  %202 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %201
  %203 = getelementptr inbounds %struct.Edge, ptr %202, i32 0, i32 1
  %204 = call noundef i64 @_ZNSt3setIiSt4lessIiESaIiEE5eraseERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %203)
  br label %205

205:                                              ; preds = %199
  %206 = load i32, ptr %12, align 4, !tbaa !5
  %207 = sext i32 %206 to i64
  %208 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %207
  %209 = getelementptr inbounds %struct.Edge, ptr %208, i32 0, i32 0
  %210 = load i32, ptr %209, align 8, !tbaa !14
  store i32 %210, ptr %12, align 4, !tbaa !5
  br label %195, !llvm.loop !18

211:                                              ; preds = %198
  %212 = load i32, ptr %8, align 4, !tbaa !5
  %213 = xor i32 %212, -1
  %214 = and i32 %213, 1
  %215 = icmp ne i32 %214, 0
  br i1 %215, label %216, label %256

216:                                              ; preds = %211
  %217 = load i32, ptr %8, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 8, ptr %13) #10
  %218 = call ptr @_ZNKSt3setIiSt4lessIiESaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  %219 = getelementptr inbounds %"struct.std::_Rb_tree_const_iterator", ptr %13, i32 0, i32 0
  store ptr %218, ptr %219, align 8
  %220 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNKSt23_Rb_tree_const_iteratorIiEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %13) #10
  %221 = load i32, ptr %220, align 4, !tbaa !5
  %222 = sub nsw i32 %217, %221
  %223 = add nsw i32 %222, 1
  %224 = load i32, ptr %8, align 4, !tbaa !5
  %225 = ashr i32 %224, 1
  %226 = sext i32 %225 to i64
  %227 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %226
  store i32 %223, ptr %227, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 8, ptr %13) #10
  %228 = load i32, ptr %8, align 4, !tbaa !5
  %229 = ashr i32 %228, 1
  %230 = icmp ne i32 %229, 0
  br i1 %230, label %231, label %255

231:                                              ; preds = %216
  %232 = load i32, ptr %8, align 4, !tbaa !5
  %233 = ashr i32 %232, 1
  %234 = sext i32 %233 to i64
  %235 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %234
  %236 = load i32, ptr %235, align 4, !tbaa !5
  %237 = load i32, ptr %8, align 4, !tbaa !5
  %238 = ashr i32 %237, 1
  %239 = sub nsw i32 %238, 1
  %240 = sext i32 %239 to i64
  %241 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %240
  %242 = load i32, ptr %241, align 4, !tbaa !5
  %243 = icmp slt i32 %236, %242
  br i1 %243, label %244, label %255

244:                                              ; preds = %231
  %245 = load i32, ptr %8, align 4, !tbaa !5
  %246 = ashr i32 %245, 1
  %247 = sub nsw i32 %246, 1
  %248 = sext i32 %247 to i64
  %249 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %248
  %250 = load i32, ptr %249, align 4, !tbaa !5
  %251 = load i32, ptr %8, align 4, !tbaa !5
  %252 = ashr i32 %251, 1
  %253 = sext i32 %252 to i64
  %254 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %253
  store i32 %250, ptr %254, align 4, !tbaa !5
  br label %255

255:                                              ; preds = %244, %231, %216
  br label %256

256:                                              ; preds = %255, %211
  br label %257

257:                                              ; preds = %256
  %258 = load i32, ptr %8, align 4, !tbaa !5
  %259 = add nsw i32 %258, 1
  store i32 %259, ptr %8, align 4, !tbaa !5
  br label %153, !llvm.loop !19

260:                                              ; preds = %159
  call void @llvm.lifetime.start.p0(i64 48, ptr %14) #10
  call void @llvm.memset.p0.i64(ptr align 8 %14, i8 0, i64 48, i1 false)
  call void @_ZNSt3setIiSt4lessIiESaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(48) %14) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEE4swapERS3_(ptr noundef nonnull align 8 dereferenceable(48) %14, ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(48) %14) #10
  call void @llvm.lifetime.end.p0(i64 48, ptr %14) #10
  store i32 0, ptr @tot, align 4, !tbaa !5
  %261 = load i32, ptr @n, align 4, !tbaa !5
  %262 = shl i32 %261, 1
  %263 = sext i32 %262 to i64
  %264 = mul i64 %263, 4
  call void @llvm.memset.p0.i64(ptr align 16 @lnk, i8 -1, i64 %264, i1 false)
  call void @llvm.lifetime.start.p0(i64 4, ptr %15) #10
  %265 = load i32, ptr @n, align 4, !tbaa !5
  %266 = sub nsw i32 %265, 1
  %267 = shl i32 %266, 1
  store i32 %267, ptr %15, align 4, !tbaa !5
  br label %268

268:                                              ; preds = %369, %260
  %269 = load i32, ptr %15, align 4, !tbaa !5
  %270 = icmp sge i32 %269, 0
  br i1 %270, label %272, label %271

271:                                              ; preds = %268
  store i32 19, ptr %9, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %15) #10
  br label %372

272:                                              ; preds = %268
  %273 = call { ptr, i8 } @_ZNSt3setIiSt4lessIiESaIiEE6insertERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %15)
  %274 = getelementptr inbounds { ptr, i8 }, ptr %16, i32 0, i32 0
  %275 = extractvalue { ptr, i8 } %273, 0
  store ptr %275, ptr %274, align 8
  %276 = getelementptr inbounds { ptr, i8 }, ptr %16, i32 0, i32 1
  %277 = extractvalue { ptr, i8 } %273, 1
  store i8 %277, ptr %276, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr %17) #10
  %278 = getelementptr inbounds %struct.Edge, ptr %17, i32 0, i32 0
  %279 = load i32, ptr %15, align 4, !tbaa !5
  %280 = load i32, ptr %15, align 4, !tbaa !5
  %281 = sext i32 %280 to i64
  %282 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %281
  %283 = load i32, ptr %282, align 4, !tbaa !5
  %284 = sub nsw i32 %279, %283
  %285 = sext i32 %284 to i64
  %286 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %285
  %287 = load i32, ptr %286, align 4, !tbaa !5
  store i32 %287, ptr %278, align 4, !tbaa !14
  %288 = getelementptr inbounds %struct.Edge, ptr %17, i32 0, i32 1
  %289 = load i32, ptr %15, align 4, !tbaa !5
  store i32 %289, ptr %288, align 4, !tbaa !16
  %290 = load i32, ptr @tot, align 4, !tbaa !5
  %291 = sext i32 %290 to i64
  %292 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %291
  call void @llvm.memcpy.p0.p0.i64(ptr align 8 %292, ptr align 4 %17, i64 8, i1 false), !tbaa.struct !17
  call void @llvm.lifetime.end.p0(i64 8, ptr %17) #10
  %293 = load i32, ptr @tot, align 4, !tbaa !5
  %294 = add nsw i32 %293, 1
  store i32 %294, ptr @tot, align 4, !tbaa !5
  %295 = load i32, ptr %15, align 4, !tbaa !5
  %296 = load i32, ptr %15, align 4, !tbaa !5
  %297 = sext i32 %296 to i64
  %298 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %297
  %299 = load i32, ptr %298, align 4, !tbaa !5
  %300 = sub nsw i32 %295, %299
  %301 = sext i32 %300 to i64
  %302 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %301
  store i32 %293, ptr %302, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %18) #10
  %303 = load i32, ptr %15, align 4, !tbaa !5
  %304 = sext i32 %303 to i64
  %305 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %304
  %306 = load i32, ptr %305, align 4, !tbaa !5
  store i32 %306, ptr %18, align 4, !tbaa !5
  br label %307

307:                                              ; preds = %317, %272
  %308 = load i32, ptr %18, align 4, !tbaa !5
  %309 = icmp ne i32 %308, -1
  br i1 %309, label %311, label %310

310:                                              ; preds = %307
  store i32 22, ptr %9, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %18) #10
  br label %323

311:                                              ; preds = %307
  %312 = load i32, ptr %18, align 4, !tbaa !5
  %313 = sext i32 %312 to i64
  %314 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %313
  %315 = getelementptr inbounds %struct.Edge, ptr %314, i32 0, i32 1
  %316 = call noundef i64 @_ZNSt3setIiSt4lessIiESaIiEE5eraseERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %315)
  br label %317

317:                                              ; preds = %311
  %318 = load i32, ptr %18, align 4, !tbaa !5
  %319 = sext i32 %318 to i64
  %320 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %319
  %321 = getelementptr inbounds %struct.Edge, ptr %320, i32 0, i32 0
  %322 = load i32, ptr %321, align 8, !tbaa !14
  store i32 %322, ptr %18, align 4, !tbaa !5
  br label %307, !llvm.loop !20

323:                                              ; preds = %310
  %324 = load i32, ptr %15, align 4, !tbaa !5
  %325 = xor i32 %324, -1
  %326 = and i32 %325, 1
  %327 = icmp ne i32 %326, 0
  br i1 %327, label %328, label %368

328:                                              ; preds = %323
  call void @llvm.lifetime.start.p0(i64 8, ptr %19) #10
  call void @_ZNKSt3setIiSt4lessIiESaIiEE6rbeginEv(ptr dead_on_unwind writable sret(%"class.std::reverse_iterator") align 8 %19, ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  %329 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNKSt16reverse_iteratorISt23_Rb_tree_const_iteratorIiEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %19)
  %330 = load i32, ptr %329, align 4, !tbaa !5
  %331 = load i32, ptr %15, align 4, !tbaa !5
  %332 = sub nsw i32 %330, %331
  %333 = add nsw i32 %332, 1
  %334 = load i32, ptr %15, align 4, !tbaa !5
  %335 = ashr i32 %334, 1
  %336 = sext i32 %335 to i64
  %337 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %336
  store i32 %333, ptr %337, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 8, ptr %19) #10
  %338 = load i32, ptr %15, align 4, !tbaa !5
  %339 = ashr i32 %338, 1
  %340 = add nsw i32 %339, 1
  %341 = load i32, ptr @n, align 4, !tbaa !5
  %342 = icmp slt i32 %340, %341
  br i1 %342, label %343, label %367

343:                                              ; preds = %328
  %344 = load i32, ptr %15, align 4, !tbaa !5
  %345 = ashr i32 %344, 1
  %346 = sext i32 %345 to i64
  %347 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %346
  %348 = load i32, ptr %347, align 4, !tbaa !5
  %349 = load i32, ptr %15, align 4, !tbaa !5
  %350 = ashr i32 %349, 1
  %351 = add nsw i32 %350, 1
  %352 = sext i32 %351 to i64
  %353 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %352
  %354 = load i32, ptr %353, align 4, !tbaa !5
  %355 = icmp slt i32 %348, %354
  br i1 %355, label %356, label %367

356:                                              ; preds = %343
  %357 = load i32, ptr %15, align 4, !tbaa !5
  %358 = ashr i32 %357, 1
  %359 = add nsw i32 %358, 1
  %360 = sext i32 %359 to i64
  %361 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %360
  %362 = load i32, ptr %361, align 4, !tbaa !5
  %363 = load i32, ptr %15, align 4, !tbaa !5
  %364 = ashr i32 %363, 1
  %365 = sext i32 %364 to i64
  %366 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %365
  store i32 %362, ptr %366, align 4, !tbaa !5
  br label %367

367:                                              ; preds = %356, %343, %328
  br label %368

368:                                              ; preds = %367, %323
  br label %369

369:                                              ; preds = %368
  %370 = load i32, ptr %15, align 4, !tbaa !5
  %371 = add nsw i32 %370, -1
  store i32 %371, ptr %15, align 4, !tbaa !5
  br label %268, !llvm.loop !21

372:                                              ; preds = %271
  call void @llvm.lifetime.start.p0(i64 4, ptr %20) #10
  store i32 0, ptr %20, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %21) #10
  store i32 1, ptr %21, align 4, !tbaa !5
  br label %373

373:                                              ; preds = %403, %372
  %374 = load i32, ptr %21, align 4, !tbaa !5
  %375 = load i32, ptr @n, align 4, !tbaa !5
  %376 = icmp slt i32 %374, %375
  br i1 %376, label %378, label %377

377:                                              ; preds = %373
  store i32 25, ptr %9, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %21) #10
  br label %406

378:                                              ; preds = %373
  %379 = load i32, ptr %20, align 4, !tbaa !5
  %380 = load i32, ptr %21, align 4, !tbaa !5
  %381 = sub nsw i32 %380, 1
  %382 = sext i32 %381 to i64
  %383 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %382
  %384 = load i32, ptr %383, align 4, !tbaa !5
  %385 = load i32, ptr %21, align 4, !tbaa !5
  %386 = sext i32 %385 to i64
  %387 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %386
  %388 = load i32, ptr %387, align 4, !tbaa !5
  %389 = add nsw i32 %384, %388
  %390 = icmp slt i32 %379, %389
  br i1 %390, label %391, label %402

391:                                              ; preds = %378
  %392 = load i32, ptr %21, align 4, !tbaa !5
  %393 = sub nsw i32 %392, 1
  %394 = sext i32 %393 to i64
  %395 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %394
  %396 = load i32, ptr %395, align 4, !tbaa !5
  %397 = load i32, ptr %21, align 4, !tbaa !5
  %398 = sext i32 %397 to i64
  %399 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %398
  %400 = load i32, ptr %399, align 4, !tbaa !5
  %401 = add nsw i32 %396, %400
  store i32 %401, ptr %20, align 4, !tbaa !5
  br label %402

402:                                              ; preds = %391, %378
  br label %403

403:                                              ; preds = %402
  %404 = load i32, ptr %21, align 4, !tbaa !5
  %405 = add nsw i32 %404, 1
  store i32 %405, ptr %21, align 4, !tbaa !5
  br label %373, !llvm.loop !22

406:                                              ; preds = %377
  %407 = load i32, ptr %20, align 4, !tbaa !5
  %408 = call i32 (ptr, ...) @printf(ptr noundef @.str.2, i32 noundef %407)
  call void @llvm.lifetime.end.p0(i64 4, ptr %20) #10
  br label %23, !llvm.loop !23

409:                                              ; preds = %23
  ret i32 0
}

declare i32 @__isoc99_scanf(ptr noundef, ...) #2

; Function Attrs: nounwind willreturn memory(read)
declare i64 @strlen(ptr noundef) #3

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

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

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 4 dereferenceable(4)) #5

; Function Attrs: nocallback nofree nounwind willreturn memory(argmem: write)
declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg) #6

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

; Function Attrs: mustprogress uwtable
declare dso_local { ptr, i8 } @_ZNSt3setIiSt4lessIiESaIiEE6insertERKi(ptr noundef nonnull align 8 dereferenceable(48), ptr noundef nonnull align 4 dereferenceable(4)) #7 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) #8

; Function Attrs: mustprogress uwtable
declare dso_local noundef i64 @_ZNSt3setIiSt4lessIiESaIiEE5eraseERKi(ptr noundef nonnull align 8 dereferenceable(48), ptr noundef nonnull align 4 dereferenceable(4)) #7 align 2

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

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

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNKSt3setIiSt4lessIiESaIiEE6rbeginEv(ptr dead_on_unwind noalias writable sret(%"class.std::reverse_iterator") align 8, ptr noundef nonnull align 8 dereferenceable(48)) #0 align 2

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

declare i32 @printf(ptr noundef, ...) #2

attributes #0 = { 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 #1 = { mustprogress norecurse 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 #2 = { "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 = { nounwind willreturn memory(read) "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 #4 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
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: write) }
attributes #7 = { 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 #8 = { nocallback nofree nounwind willreturn memory(argmem: readwrite) }
attributes #9 = { nounwind willreturn memory(read) }
attributes #10 = { 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 = !{!7, !7, i64 0}
!10 = distinct !{!10, !11}
!11 = !{!"llvm.loop.mustprogress"}
!12 = distinct !{!12, !11}
!13 = distinct !{!13, !11}
!14 = !{!15, !6, i64 0}
!15 = !{!"_ZTS4Edge", !6, i64 0, !6, i64 4}
!16 = !{!15, !6, i64 4}
!17 = !{i64 0, i64 4, !5, i64 4, i64 4, !5}
!18 = distinct !{!18, !11}
!19 = distinct !{!19, !11}
!20 = distinct !{!20, !11}
!21 = distinct !{!21, !11}
!22 = distinct !{!22, !11}
!23 = distinct !{!23, !11}


; 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::set" = type { %"class.std::_Rb_tree" }
%"class.std::_Rb_tree" = type { %"struct.std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>>::_Rb_tree_impl" }
%"struct.std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>>::_Rb_tree_impl" = type { [8 x i8], %"struct.std::_Rb_tree_header" }
%"struct.std::_Rb_tree_header" = type { %"struct.std::_Rb_tree_node_base", i64 }
%"struct.std::_Rb_tree_node_base" = type { i32, ptr, ptr, ptr }
%struct.Edge = type { i32, i32 }
%"struct.std::_Rb_tree_const_iterator" = type { ptr }
%"class.std::reverse_iterator" = type { %"struct.std::_Rb_tree_const_iterator" }

@t = external dso_local global i32, align 4
@n = external dso_local local_unnamed_addr global i32, align 4
@h = external dso_local global [200002 x i32], align 16
@pre = external dso_local local_unnamed_addr global [100001 x i32], align 16
@suf = external dso_local local_unnamed_addr global [100001 x i32], align 16
@tot = external dso_local local_unnamed_addr global i32, align 4
@lnk = external dso_local local_unnamed_addr global [200002 x i32], align 16
@str = external dso_local global [100001 x i8], align 16
@buf = external dso_local local_unnamed_addr global [200002 x i8], align 16
@sp = external dso_local global %"class.std::set", align 8
@e = external dso_local global [200002 x %struct.Edge], align 16
@.str = external hidden unnamed_addr constant [3 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.2 = external hidden unnamed_addr constant [4 x i8], align 1

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

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

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() local_unnamed_addr #1 {
  %1 = alloca i32, align 4
  %2 = alloca %"class.std::set", align 8
  %3 = alloca i32, align 4
  %4 = alloca %"struct.std::_Rb_tree_const_iterator", align 8
  %5 = alloca %"class.std::set", align 8
  %6 = alloca i32, align 4
  %7 = alloca %"class.std::reverse_iterator", align 8
  %8 = tail call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str, ptr noundef nonnull @t)
  %9 = load i32, ptr @t, align 4, !tbaa !5
  %10 = add nsw i32 %9, -1
  store i32 %10, ptr @t, align 4, !tbaa !5
  %.not112 = icmp eq i32 %9, 0
  br i1 %.not112, label %._crit_edge115, label %.lr.ph114

.lr.ph114:                                        ; preds = %0, %._crit_edge110
  %11 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str.1, ptr noundef nonnull @str)
  %12 = call i64 @strlen(ptr noundef nonnull dereferenceable(1) @str) #9
  %13 = trunc i64 %12 to i32
  store i32 %13, ptr @n, align 4, !tbaa !5
  %14 = icmp sgt i32 %13, 0
  br i1 %14, label %.lr.ph.preheader, label %._crit_edge

.lr.ph.preheader:                                 ; preds = %.lr.ph114
  %wide.trip.count = and i64 %12, 2147483647
  %min.iters.check147 = icmp ult i64 %wide.trip.count, 24
  br i1 %min.iters.check147, label %.lr.ph.preheader161, label %vector.scevcheck

.lr.ph.preheader161:                              ; preds = %middle.block145, %vector.scevcheck, %.lr.ph.preheader
  %indvars.iv.ph = phi i64 [ 0, %vector.scevcheck ], [ 0, %.lr.ph.preheader ], [ %n.vec150, %middle.block145 ]
  %15 = sub i64 %12, %indvars.iv.ph
  %.neg = add nsw i64 %indvars.iv.ph, 1
  %xtraiter = and i64 %15, 1
  %lcmp.mod.not = icmp eq i64 %xtraiter, 0
  br i1 %lcmp.mod.not, label %.lr.ph.prol.loopexit, label %.lr.ph.prol

.lr.ph.prol:                                      ; preds = %.lr.ph.preheader161
  %16 = getelementptr inbounds [100001 x i8], ptr @str, i64 0, i64 %indvars.iv.ph
  %17 = load i8, ptr %16, align 1, !tbaa !9
  %sext.prol = shl i64 %indvars.iv.ph, 33
  %18 = ashr exact i64 %sext.prol, 32
  %19 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %18
  store i8 %17, ptr %19, align 2, !tbaa !9
  %indvars.iv.tr.prol = trunc i64 %indvars.iv.ph to i32
  %20 = shl i32 %indvars.iv.tr.prol, 1
  %21 = or disjoint i32 %20, 1
  %22 = sext i32 %21 to i64
  %23 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %22
  store i8 35, ptr %23, align 1, !tbaa !9
  %indvars.iv.next.prol = add nuw nsw i64 %indvars.iv.ph, 1
  br label %.lr.ph.prol.loopexit

.lr.ph.prol.loopexit:                             ; preds = %.lr.ph.prol, %.lr.ph.preheader161
  %indvars.iv.unr = phi i64 [ %indvars.iv.ph, %.lr.ph.preheader161 ], [ %indvars.iv.next.prol, %.lr.ph.prol ]
  %24 = icmp eq i64 %wide.trip.count, %.neg
  br i1 %24, label %._crit_edge, label %.lr.ph

vector.scevcheck:                                 ; preds = %.lr.ph.preheader
  %25 = add nsw i64 %wide.trip.count, -1
  %26 = and i64 %25, -3221225472
  %27 = icmp ne i64 %26, 0
  %mul.result140 = shl nsw i64 %25, 1
  %28 = getelementptr i8, ptr @buf, i64 %mul.result140
  %29 = icmp ult ptr %28, @buf
  %mul.result143 = shl nsw i64 %25, 1
  %30 = getelementptr i8, ptr getelementptr inbounds (i8, ptr @buf, i64 1), i64 %mul.result143
  %31 = icmp ult ptr %30, getelementptr inbounds (i8, ptr @buf, i64 1)
  %32 = or i1 %27, %29
  %33 = or i1 %32, %31
  br i1 %33, label %.lr.ph.preheader161, label %vector.ph148

vector.ph148:                                     ; preds = %vector.scevcheck
  %n.mod.vf149 = and i64 %12, 15
  %n.vec150 = sub nsw i64 %wide.trip.count, %n.mod.vf149
  br label %vector.body152

vector.body152:                                   ; preds = %vector.body152, %vector.ph148
  %index153 = phi i64 [ 0, %vector.ph148 ], [ %index.next157, %vector.body152 ]
  %34 = trunc i64 %index153 to i32
  %35 = getelementptr inbounds [100001 x i8], ptr @str, i64 0, i64 %index153
  %36 = getelementptr inbounds i8, ptr %35, i64 8
  %wide.load154 = load <8 x i8>, ptr %35, align 16, !tbaa !9
  %wide.load155 = load <8 x i8>, ptr %36, align 8, !tbaa !9
  %37 = shl i32 %34, 1
  %38 = shl i32 %34, 1
  %39 = or disjoint i32 %37, 1
  %40 = or disjoint i32 %38, 17
  %41 = sext i32 %39 to i64
  %42 = sext i32 %40 to i64
  %gep = getelementptr [200002 x i8], ptr getelementptr (i8, ptr @buf, i64 -1), i64 0, i64 %41
  %gep168 = getelementptr [200002 x i8], ptr getelementptr (i8, ptr @buf, i64 -1), i64 0, i64 %42
  %interleaved.vec = shufflevector <8 x i8> %wide.load154, <8 x i8> <i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35>, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
  store <16 x i8> %interleaved.vec, ptr %gep, align 2, !tbaa !9
  %interleaved.vec156 = shufflevector <8 x i8> %wide.load155, <8 x i8> <i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35>, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
  store <16 x i8> %interleaved.vec156, ptr %gep168, align 2, !tbaa !9
  %index.next157 = add nuw i64 %index153, 16
  %43 = icmp eq i64 %index.next157, %n.vec150
  br i1 %43, label %middle.block145, label %vector.body152, !llvm.loop !10

middle.block145:                                  ; preds = %vector.body152
  %cmp.n158 = icmp eq i64 %n.mod.vf149, 0
  br i1 %cmp.n158, label %._crit_edge, label %.lr.ph.preheader161

._crit_edge:                                      ; preds = %.lr.ph.prol.loopexit, %.lr.ph, %middle.block145, %.lr.ph114
  %44 = shl i32 %13, 1
  %45 = add i32 %44, -1
  %46 = sext i32 %45 to i64
  %47 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %46
  store i8 0, ptr %47, align 1, !tbaa !9
  %48 = add i32 %44, -2
  %.not6380 = icmp slt i32 %48, 0
  br i1 %.not6380, label %._crit_edge86, label %.lr.ph85

.lr.ph:                                           ; preds = %.lr.ph.prol.loopexit, %.lr.ph
  %indvars.iv = phi i64 [ %indvars.iv.next.1, %.lr.ph ], [ %indvars.iv.unr, %.lr.ph.prol.loopexit ]
  %49 = getelementptr inbounds [100001 x i8], ptr @str, i64 0, i64 %indvars.iv
  %50 = load i8, ptr %49, align 1, !tbaa !9
  %sext = shl i64 %indvars.iv, 33
  %51 = ashr exact i64 %sext, 32
  %52 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %51
  store i8 %50, ptr %52, align 2, !tbaa !9
  %indvars.iv.tr = trunc i64 %indvars.iv to i32
  %53 = shl i32 %indvars.iv.tr, 1
  %54 = or disjoint i32 %53, 1
  %55 = sext i32 %54 to i64
  %56 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %55
  store i8 35, ptr %56, align 1, !tbaa !9
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %57 = getelementptr inbounds [100001 x i8], ptr @str, i64 0, i64 %indvars.iv.next
  %58 = load i8, ptr %57, align 1, !tbaa !9
  %sext.1 = shl i64 %indvars.iv.next, 33
  %59 = ashr exact i64 %sext.1, 32
  %60 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %59
  store i8 %58, ptr %60, align 2, !tbaa !9
  %indvars.iv.tr.1 = trunc i64 %indvars.iv.next to i32
  %61 = shl i32 %indvars.iv.tr.1, 1
  %62 = or disjoint i32 %61, 1
  %63 = sext i32 %62 to i64
  %64 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %63
  store i8 35, ptr %64, align 1, !tbaa !9
  %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2
  %exitcond.not.1 = icmp eq i64 %indvars.iv.next.1, %wide.trip.count
  br i1 %exitcond.not.1, label %._crit_edge, label %.lr.ph, !llvm.loop !14

._crit_edge86:                                    ; preds = %.critedge, %._crit_edge
  call void @llvm.lifetime.start.p0(i64 48, ptr nonnull %2) #10
  call void @llvm.memset.p0.i64(ptr noundef nonnull align 8 dereferenceable(48) %2, i8 0, i64 48, i1 false)
  call void @_ZNSt3setIiSt4lessIiESaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(48) %2) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEE4swapERS3_(ptr noundef nonnull align 8 dereferenceable(48) %2, ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(48) %2) #10
  call void @llvm.lifetime.end.p0(i64 48, ptr nonnull %2) #10
  store i32 0, ptr @tot, align 4, !tbaa !5
  %65 = load i32, ptr @n, align 4, !tbaa !5
  %66 = shl i32 %65, 1
  %67 = sext i32 %66 to i64
  %68 = shl nsw i64 %67, 2
  call void @llvm.memset.p0.i64(ptr nonnull align 16 @lnk, i8 -1, i64 %68, i1 false)
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %3) #10
  store i32 0, ptr %3, align 4, !tbaa !5
  %69 = add i32 %66, -2
  %.not6493 = icmp slt i32 %69, 0
  br i1 %.not6493, label %._crit_edge96, label %.lr.ph95

.lr.ph85:                                         ; preds = %._crit_edge, %.critedge
  %indvars.iv122 = phi i64 [ %indvars.iv.next123, %.critedge ], [ 0, %._crit_edge ]
  %indvars.iv119 = phi i32 [ %indvars.iv.next120, %.critedge ], [ 1, %._crit_edge ]
  %.05082 = phi i32 [ %spec.select72, %.critedge ], [ 0, %._crit_edge ]
  %.05281 = phi i32 [ %spec.select, %.critedge ], [ 0, %._crit_edge ]
  %70 = sext i32 %.05082 to i64
  %71 = icmp slt i64 %indvars.iv122, %70
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %1) #10
  br i1 %71, label %72, label %81

72:                                               ; preds = %.lr.ph85
  %73 = trunc nuw nsw i64 %indvars.iv122 to i32
  %74 = sub nsw i32 %.05082, %73
  store i32 %74, ptr %1, align 4, !tbaa !5
  %75 = shl i32 %.05281, 1
  %76 = sext i32 %75 to i64
  %77 = sub nsw i64 %76, %indvars.iv122
  %78 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %77
  %79 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4) %1, ptr noundef nonnull align 4 dereferenceable(4) %78)
  %80 = load i32, ptr %79, align 4, !tbaa !5
  br label %81

81:                                               ; preds = %.lr.ph85, %72
  %82 = phi i32 [ %80, %72 ], [ 0, %.lr.ph85 ]
  %83 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %indvars.iv122
  store i32 %82, ptr %83, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %1) #10
  %84 = sext i32 %82 to i64
  %.not7175 = icmp slt i64 %indvars.iv122, %84
  br i1 %.not7175, label %.critedge, label %.lr.ph77

.lr.ph77:                                         ; preds = %81, %92
  %indvars.iv117 = phi i64 [ %indvars.iv.next118, %92 ], [ %84, %81 ]
  %85 = sub nsw i64 %indvars.iv122, %indvars.iv117
  %86 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %85
  %87 = load i8, ptr %86, align 1, !tbaa !9
  %88 = add nsw i64 %indvars.iv117, %indvars.iv122
  %89 = getelementptr inbounds [200002 x i8], ptr @buf, i64 0, i64 %88
  %90 = load i8, ptr %89, align 1, !tbaa !9
  %91 = icmp eq i8 %87, %90
  br i1 %91, label %92, label %.critedge.loopexit.split.loop.exit132

92:                                               ; preds = %.lr.ph77
  %indvars.iv.next118 = add nsw i64 %indvars.iv117, 1
  %93 = trunc nsw i64 %indvars.iv.next118 to i32
  store i32 %93, ptr %83, align 4, !tbaa !5
  %.not71.not = icmp slt i64 %indvars.iv117, %indvars.iv122
  br i1 %.not71.not, label %.lr.ph77, label %.critedge, !llvm.loop !15

.critedge.loopexit.split.loop.exit132:            ; preds = %.lr.ph77
  %94 = trunc nsw i64 %indvars.iv117 to i32
  br label %.critedge

.critedge:                                        ; preds = %92, %.critedge.loopexit.split.loop.exit132, %81
  %.lcssa = phi i32 [ %82, %81 ], [ %94, %.critedge.loopexit.split.loop.exit132 ], [ %indvars.iv119, %92 ]
  %95 = trunc nuw nsw i64 %indvars.iv122 to i32
  %96 = add nsw i32 %.lcssa, %95
  %97 = icmp slt i32 %.05082, %96
  %spec.select = select i1 %97, i32 %95, i32 %.05281
  %spec.select72 = call i32 @llvm.smax.i32(i32 %.05082, i32 %96)
  %indvars.iv.next123 = add nuw nsw i64 %indvars.iv122, 1
  %98 = load i32, ptr @n, align 4, !tbaa !5
  %99 = shl i32 %98, 1
  %100 = add i32 %99, -2
  %101 = sext i32 %100 to i64
  %.not63.not = icmp slt i64 %indvars.iv122, %101
  %indvars.iv.next120 = add nuw i32 %indvars.iv119, 1
  br i1 %.not63.not, label %.lr.ph85, label %._crit_edge86, !llvm.loop !16

._crit_edge96:                                    ; preds = %145, %._crit_edge86
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %3) #10
  call void @llvm.lifetime.start.p0(i64 48, ptr nonnull %5) #10
  call void @llvm.memset.p0.i64(ptr noundef nonnull align 8 dereferenceable(48) %5, i8 0, i64 48, i1 false)
  call void @_ZNSt3setIiSt4lessIiESaIiEEC2Ev(ptr noundef nonnull align 8 dereferenceable(48) %5) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEE4swapERS3_(ptr noundef nonnull align 8 dereferenceable(48) %5, ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  call void @_ZNSt3setIiSt4lessIiESaIiEED2Ev(ptr noundef nonnull align 8 dereferenceable(48) %5) #10
  call void @llvm.lifetime.end.p0(i64 48, ptr nonnull %5) #10
  store i32 0, ptr @tot, align 4, !tbaa !5
  %102 = load i32, ptr @n, align 4, !tbaa !5
  %103 = shl i32 %102, 1
  %104 = sext i32 %103 to i64
  %105 = shl nsw i64 %104, 2
  call void @llvm.memset.p0.i64(ptr nonnull align 16 @lnk, i8 -1, i64 %105, i1 false)
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %6) #10
  %106 = add i32 %103, -2
  store i32 %106, ptr %6, align 4, !tbaa !5
  %107 = icmp sgt i32 %106, -1
  br i1 %107, label %.lr.ph104, label %._crit_edge105

.lr.ph95:                                         ; preds = %._crit_edge86, %145
  %108 = call { ptr, i8 } @_ZNSt3setIiSt4lessIiESaIiEE6insertERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %3)
  %109 = load i32, ptr %3, align 4, !tbaa !5
  %110 = sext i32 %109 to i64
  %111 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %110
  %112 = load i32, ptr %111, align 4, !tbaa !5
  %113 = add nsw i32 %112, %109
  %114 = sext i32 %113 to i64
  %115 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %114
  %116 = load i32, ptr %115, align 4, !tbaa !5
  %117 = load i32, ptr @tot, align 4, !tbaa !5
  %118 = sext i32 %117 to i64
  %119 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %118
  store i32 %116, ptr %119, align 8, !tbaa !5
  %.sroa.416.0..sroa_idx = getelementptr inbounds i8, ptr %119, i64 4
  store i32 %109, ptr %.sroa.416.0..sroa_idx, align 4, !tbaa !5
  %120 = add nsw i32 %117, 1
  store i32 %120, ptr @tot, align 4, !tbaa !5
  store i32 %117, ptr %115, align 4, !tbaa !5
  %121 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %110
  %.05487 = load i32, ptr %121, align 4, !tbaa !5
  %.not6888 = icmp eq i32 %.05487, -1
  br i1 %.not6888, label %._crit_edge92, label %.lr.ph91

._crit_edge92.loopexit:                           ; preds = %.lr.ph91
  %.pre = load i32, ptr %3, align 4, !tbaa !5
  br label %._crit_edge92

._crit_edge92:                                    ; preds = %._crit_edge92.loopexit, %.lr.ph95
  %122 = phi i32 [ %.pre, %._crit_edge92.loopexit ], [ %109, %.lr.ph95 ]
  %123 = and i32 %122, 1
  %.not69.not = icmp eq i32 %123, 0
  br i1 %.not69.not, label %128, label %145

.lr.ph91:                                         ; preds = %.lr.ph95, %.lr.ph91
  %.05489 = phi i32 [ %.054, %.lr.ph91 ], [ %.05487, %.lr.ph95 ]
  %124 = sext i32 %.05489 to i64
  %125 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %124
  %126 = getelementptr inbounds i8, ptr %125, i64 4
  %127 = call noundef i64 @_ZNSt3setIiSt4lessIiESaIiEE5eraseERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %126)
  %.054 = load i32, ptr %125, align 8, !tbaa !5
  %.not68 = icmp eq i32 %.054, -1
  br i1 %.not68, label %._crit_edge92.loopexit, label %.lr.ph91, !llvm.loop !17

128:                                              ; preds = %._crit_edge92
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %4) #10
  %129 = call ptr @_ZNKSt3setIiSt4lessIiESaIiEE5beginEv(ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  store ptr %129, ptr %4, align 8
  %130 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNKSt23_Rb_tree_const_iteratorIiEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %4) #10
  %131 = load i32, ptr %130, align 4, !tbaa !5
  %132 = sub nsw i32 %122, %131
  %133 = add nsw i32 %132, 1
  %134 = load i32, ptr %3, align 4, !tbaa !5
  %135 = ashr i32 %134, 1
  %136 = sext i32 %135 to i64
  %137 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %136
  store i32 %133, ptr %137, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %4) #10
  %.not70 = icmp ult i32 %134, 2
  br i1 %.not70, label %145, label %138

138:                                              ; preds = %128
  %139 = add nsw i32 %135, -1
  %140 = sext i32 %139 to i64
  %141 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %140
  %142 = load i32, ptr %141, align 4, !tbaa !5
  %143 = icmp slt i32 %133, %142
  br i1 %143, label %144, label %145

144:                                              ; preds = %138
  store i32 %142, ptr %137, align 4, !tbaa !5
  br label %145

145:                                              ; preds = %._crit_edge92, %144, %138, %128
  %146 = phi i32 [ %122, %._crit_edge92 ], [ %134, %144 ], [ %134, %138 ], [ %134, %128 ]
  %147 = add nsw i32 %146, 1
  store i32 %147, ptr %3, align 4, !tbaa !5
  %148 = load i32, ptr @n, align 4, !tbaa !5
  %149 = shl i32 %148, 1
  %150 = add i32 %149, -2
  %.not64.not = icmp slt i32 %146, %150
  br i1 %.not64.not, label %.lr.ph95, label %._crit_edge96, !llvm.loop !18

._crit_edge105.loopexit:                          ; preds = %202
  %.pre131 = load i32, ptr @n, align 4, !tbaa !5
  br label %._crit_edge105

._crit_edge105:                                   ; preds = %._crit_edge105.loopexit, %._crit_edge96
  %151 = phi i32 [ %.pre131, %._crit_edge105.loopexit ], [ %102, %._crit_edge96 ]
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %6) #10
  %152 = icmp sgt i32 %151, 1
  br i1 %152, label %.lr.ph109.preheader, label %._crit_edge110

.lr.ph109.preheader:                              ; preds = %._crit_edge105
  %wide.trip.count128 = zext nneg i32 %151 to i64
  %153 = add nsw i64 %wide.trip.count128, -1
  %min.iters.check = icmp ult i32 %151, 9
  br i1 %min.iters.check, label %.lr.ph109.preheader160, label %vector.ph

.lr.ph109.preheader160:                           ; preds = %middle.block, %.lr.ph109.preheader
  %indvars.iv125.ph = phi i64 [ 1, %.lr.ph109.preheader ], [ %ind.end, %middle.block ]
  %.046106.ph = phi i32 [ 0, %.lr.ph109.preheader ], [ %163, %middle.block ]
  br label %.lr.ph109

vector.ph:                                        ; preds = %.lr.ph109.preheader
  %n.vec = and i64 %153, -8
  %ind.end = or disjoint i64 %n.vec, 1
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %vec.phi = phi <4 x i32> [ zeroinitializer, %vector.ph ], [ %160, %vector.body ]
  %vec.phi135 = phi <4 x i32> [ zeroinitializer, %vector.ph ], [ %161, %vector.body ]
  %offset.idx = or disjoint i64 %index, 1
  %154 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %index
  %155 = getelementptr inbounds i8, ptr %154, i64 16
  %wide.load = load <4 x i32>, ptr %154, align 16, !tbaa !5
  %wide.load136 = load <4 x i32>, ptr %155, align 16, !tbaa !5
  %156 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %offset.idx
  %157 = getelementptr inbounds i8, ptr %156, i64 16
  %wide.load137 = load <4 x i32>, ptr %156, align 4, !tbaa !5
  %wide.load138 = load <4 x i32>, ptr %157, align 4, !tbaa !5
  %158 = add nsw <4 x i32> %wide.load137, %wide.load
  %159 = add nsw <4 x i32> %wide.load138, %wide.load136
  %160 = call <4 x i32> @llvm.smax.v4i32(<4 x i32> %vec.phi, <4 x i32> %158)
  %161 = call <4 x i32> @llvm.smax.v4i32(<4 x i32> %vec.phi135, <4 x i32> %159)
  %index.next = add nuw i64 %index, 8
  %162 = icmp eq i64 %index.next, %n.vec
  br i1 %162, label %middle.block, label %vector.body, !llvm.loop !19

middle.block:                                     ; preds = %vector.body
  %rdx.minmax = call <4 x i32> @llvm.smax.v4i32(<4 x i32> %160, <4 x i32> %161)
  %163 = call i32 @llvm.vector.reduce.smax.v4i32(<4 x i32> %rdx.minmax)
  %cmp.n = icmp eq i64 %153, %n.vec
  br i1 %cmp.n, label %._crit_edge110, label %.lr.ph109.preheader160

.lr.ph104:                                        ; preds = %._crit_edge96, %202
  %164 = call { ptr, i8 } @_ZNSt3setIiSt4lessIiESaIiEE6insertERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %6)
  %165 = load i32, ptr %6, align 4, !tbaa !5
  %166 = sext i32 %165 to i64
  %167 = getelementptr inbounds [200002 x i32], ptr @h, i64 0, i64 %166
  %168 = load i32, ptr %167, align 4, !tbaa !5
  %169 = sub nsw i32 %165, %168
  %170 = sext i32 %169 to i64
  %171 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %170
  %172 = load i32, ptr %171, align 4, !tbaa !5
  %173 = load i32, ptr @tot, align 4, !tbaa !5
  %174 = sext i32 %173 to i64
  %175 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %174
  store i32 %172, ptr %175, align 8, !tbaa !5
  %.sroa.4.0..sroa_idx = getelementptr inbounds i8, ptr %175, i64 4
  store i32 %165, ptr %.sroa.4.0..sroa_idx, align 4, !tbaa !5
  %176 = add nsw i32 %173, 1
  store i32 %176, ptr @tot, align 4, !tbaa !5
  store i32 %173, ptr %171, align 4, !tbaa !5
  %177 = getelementptr inbounds [200002 x i32], ptr @lnk, i64 0, i64 %166
  %.04797 = load i32, ptr %177, align 4, !tbaa !5
  %.not6698 = icmp eq i32 %.04797, -1
  br i1 %.not6698, label %._crit_edge102, label %.lr.ph101

._crit_edge102.loopexit:                          ; preds = %.lr.ph101
  %.pre130 = load i32, ptr %6, align 4, !tbaa !5
  br label %._crit_edge102

._crit_edge102:                                   ; preds = %._crit_edge102.loopexit, %.lr.ph104
  %178 = phi i32 [ %.pre130, %._crit_edge102.loopexit ], [ %165, %.lr.ph104 ]
  %179 = and i32 %178, 1
  %.not67.not = icmp eq i32 %179, 0
  br i1 %.not67.not, label %184, label %202

.lr.ph101:                                        ; preds = %.lr.ph104, %.lr.ph101
  %.04799 = phi i32 [ %.047, %.lr.ph101 ], [ %.04797, %.lr.ph104 ]
  %180 = sext i32 %.04799 to i64
  %181 = getelementptr inbounds [200002 x %struct.Edge], ptr @e, i64 0, i64 %180
  %182 = getelementptr inbounds i8, ptr %181, i64 4
  %183 = call noundef i64 @_ZNSt3setIiSt4lessIiESaIiEE5eraseERKi(ptr noundef nonnull align 8 dereferenceable(48) @sp, ptr noundef nonnull align 4 dereferenceable(4) %182)
  %.047 = load i32, ptr %181, align 8, !tbaa !5
  %.not66 = icmp eq i32 %.047, -1
  br i1 %.not66, label %._crit_edge102.loopexit, label %.lr.ph101, !llvm.loop !20

184:                                              ; preds = %._crit_edge102
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %7) #10
  call void @_ZNKSt3setIiSt4lessIiESaIiEE6rbeginEv(ptr dead_on_unwind nonnull writable sret(%"class.std::reverse_iterator") align 8 %7, ptr noundef nonnull align 8 dereferenceable(48) @sp) #10
  %185 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZNKSt16reverse_iteratorISt23_Rb_tree_const_iteratorIiEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %7)
  %186 = load i32, ptr %185, align 4, !tbaa !5
  %187 = load i32, ptr %6, align 4, !tbaa !5
  %188 = sub nsw i32 %186, %187
  %189 = add nsw i32 %188, 1
  %190 = ashr i32 %187, 1
  %191 = sext i32 %190 to i64
  %192 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %191
  store i32 %189, ptr %192, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %7) #10
  %193 = add nsw i32 %190, 1
  %194 = load i32, ptr @n, align 4, !tbaa !5
  %195 = icmp slt i32 %193, %194
  br i1 %195, label %196, label %202

196:                                              ; preds = %184
  %197 = sext i32 %193 to i64
  %198 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %197
  %199 = load i32, ptr %198, align 4, !tbaa !5
  %200 = icmp slt i32 %189, %199
  br i1 %200, label %201, label %202

201:                                              ; preds = %196
  store i32 %199, ptr %192, align 4, !tbaa !5
  br label %202

202:                                              ; preds = %._crit_edge102, %201, %196, %184
  %203 = phi i32 [ %178, %._crit_edge102 ], [ %187, %201 ], [ %187, %196 ], [ %187, %184 ]
  %204 = add nsw i32 %203, -1
  store i32 %204, ptr %6, align 4, !tbaa !5
  %205 = icmp sgt i32 %203, 0
  br i1 %205, label %.lr.ph104, label %._crit_edge105.loopexit, !llvm.loop !21

._crit_edge110:                                   ; preds = %.lr.ph109, %middle.block, %._crit_edge105
  %.046.lcssa = phi i32 [ 0, %._crit_edge105 ], [ %163, %middle.block ], [ %spec.select73, %.lr.ph109 ]
  %206 = call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str.2, i32 noundef %.046.lcssa)
  %207 = load i32, ptr @t, align 4, !tbaa !5
  %208 = add nsw i32 %207, -1
  store i32 %208, ptr @t, align 4, !tbaa !5
  %.not = icmp eq i32 %207, 0
  br i1 %.not, label %._crit_edge115, label %.lr.ph114, !llvm.loop !22

.lr.ph109:                                        ; preds = %.lr.ph109.preheader160, %.lr.ph109
  %indvars.iv125 = phi i64 [ %indvars.iv.next126, %.lr.ph109 ], [ %indvars.iv125.ph, %.lr.ph109.preheader160 ]
  %.046106 = phi i32 [ %spec.select73, %.lr.ph109 ], [ %.046106.ph, %.lr.ph109.preheader160 ]
  %209 = add nsw i64 %indvars.iv125, -1
  %210 = getelementptr inbounds [100001 x i32], ptr @pre, i64 0, i64 %209
  %211 = load i32, ptr %210, align 4, !tbaa !5
  %212 = getelementptr inbounds [100001 x i32], ptr @suf, i64 0, i64 %indvars.iv125
  %213 = load i32, ptr %212, align 4, !tbaa !5
  %214 = add nsw i32 %213, %211
  %spec.select73 = call i32 @llvm.smax.i32(i32 %.046106, i32 %214)
  %indvars.iv.next126 = add nuw nsw i64 %indvars.iv125, 1
  %exitcond129.not = icmp eq i64 %indvars.iv.next126, %wide.trip.count128
  br i1 %exitcond129.not, label %._crit_edge110, label %.lr.ph109, !llvm.loop !23

._crit_edge115:                                   ; preds = %._crit_edge110, %0
  ret i32 0
}

; Function Attrs: nofree nounwind
declare noundef i32 @__isoc99_scanf(ptr nocapture noundef readonly, ...) local_unnamed_addr #2

; Function Attrs: mustprogress nofree nounwind willreturn memory(argmem: read)
declare i64 @strlen(ptr nocapture noundef) local_unnamed_addr #3

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

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

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 4 dereferenceable(4)) local_unnamed_addr #5

; Function Attrs: mustprogress nocallback nofree nounwind willreturn memory(argmem: write)
declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg) #6

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

; Function Attrs: mustprogress uwtable
declare dso_local { ptr, i8 } @_ZNSt3setIiSt4lessIiESaIiEE6insertERKi(ptr noundef nonnull align 8 dereferenceable(48), ptr noundef nonnull align 4 dereferenceable(4)) local_unnamed_addr #7 align 2

; Function Attrs: mustprogress uwtable
declare dso_local noundef i64 @_ZNSt3setIiSt4lessIiESaIiEE5eraseERKi(ptr noundef nonnull align 8 dereferenceable(48), ptr noundef nonnull align 4 dereferenceable(4)) local_unnamed_addr #7 align 2

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

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

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNKSt3setIiSt4lessIiESaIiEE6rbeginEv(ptr dead_on_unwind noalias writable sret(%"class.std::reverse_iterator") align 8, ptr noundef nonnull align 8 dereferenceable(48)) local_unnamed_addr #0 align 2

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

; Function Attrs: nofree nounwind
declare noundef i32 @printf(ptr nocapture noundef readonly, ...) local_unnamed_addr #2

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

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare <4 x i32> @llvm.smax.v4i32(<4 x i32>, <4 x i32>) #8

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.vector.reduce.smax.v4i32(<4 x i32>) #8

attributes #0 = { 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 #1 = { mustprogress norecurse 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 #2 = { nofree 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 #3 = { mustprogress nofree nounwind willreturn memory(argmem: read) "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 #4 = { mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
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 = { mustprogress nocallback nofree nounwind willreturn memory(argmem: write) }
attributes #7 = { 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 #8 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
attributes #9 = { nounwind willreturn memory(read) }
attributes #10 = { 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 = !{!7, !7, i64 0}
!10 = distinct !{!10, !11, !12, !13}
!11 = !{!"llvm.loop.mustprogress"}
!12 = !{!"llvm.loop.isvectorized", i32 1}
!13 = !{!"llvm.loop.unroll.runtime.disable"}
!14 = distinct !{!14, !11, !12}
!15 = distinct !{!15, !11}
!16 = distinct !{!16, !11}
!17 = distinct !{!17, !11}
!18 = distinct !{!18, !11}
!19 = distinct !{!19, !11, !12, !13}
!20 = distinct !{!20, !11}
!21 = distinct !{!21, !11}
!22 = distinct !{!22, !11}
!23 = distinct !{!23, !11, !13, !12}


; Effective O3 passes: EarlyCSEPass,GVNPass,GlobalDCEPass,GlobalOptPass,IPSCCPPass,IndVarSimplifyPass,InferAlignmentPass,InferFunctionAttrsPass,InstCombinePass,InstSimplifyPass,JumpThreadingPass,LCSSAPass,LICMPass,LoopLoadEliminationPass,LoopRotatePass,LoopSimplifyPass,LoopUnrollPass,LoopVectorizePass,ReassociatePass,SROAPass,SimplifyCFGPass,TailCallElimPass