C. Дзи физикт дуртай

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дзи физикт дуртай. Тэр нягтыг тооцон бодох дуртай.

Бараг бүх зүйлд нягт байдаг, графад ч бас. Чиглэлт бус графын нягтыг дараах байдлаар тодорхойлъё: (графын ирмэг болон орой нь ямар нэгэн утгатай байдаг)

Энд $v$ бол оройнуудын нийлбэр, $e$ бол ирмэгүүдийн нийлбэр.

Дзид $G$ граф байв. Одоо тэр уг графын дэд граф болдог, холбоотой граф $G'$-г олохыг хүсч байна. Энд $G'$-ийн нягт аль болох их байна.

$G(V, E)$ графын $G'(V', E')$ дэд граф нь дараах нөхцөлүүдийг хангасан байна. Үүнд:

  • ;
  • Хэрэв ба ирмэг байвал ирмэг байна;
  • $G'$ дэх ирмэгийн утга харгалзах $G$ дэх ирмэгийн утгатай ижил бол энэ нь зангилааны утга болно.

Дзид хамгийн их нягтралтай дэд графыг олоход туслаарай. Таны олсон дэд граф холбоотой байх ёстой гэдгийг анхаараарай.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n (1≤n≤500)$, 2 бүхэл тоог агуулна. $n$ бүхэл тоо нь $G$ графын зангилааны тоо, $m$ нь ирмэгийн тоог харуулна.

Дараагийн мөр нь $n$ ширхэг, зайгаар тусгаарлагдсан $x_{i} (1≤x_{i}≤10^{6})$ бүхэл тоонуудыг агуулна. Энд, $x_{i}$ нь $i$-р зангилааны утгыг харуулна. Графын зангилаануудыг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.

Дараагийн $m$ мөрүүд тус бүр нь зайгаар тусгаарлагдсан $a_{i}, b_{i}, c_{i} (1≤a_{i}

Гаралт

Хариуг дүрслэх, харьцангуй болон үнэмлэхүй алдаа нь хамгийн багадаа $10^{ - 9}$ байх бодит тоог хэвлээрэй.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
1 0
1
Гаралт
0.000000000000000
Оролт
2 1
1 2
1 2 1
Гаралт
3.000000000000000
Оролт
5 6
13 56 73 98 17
1 2 56
1 3 29
1 4 42
2 3 95
2 4 88
3 4 63
Гаралт
2.965517241379311

Тэмдэглэл

Эхний жишээнд, та хоосон эсвэл зөвхөн $1$ зангилаатай дэд графыг сонгож болох юм.

Хоёр дахь жишээнд графыг бүхлээр нь сонгох хэрэгтэй.

Сэтгэгдлүүдийг ачааллаж байна...