musou1500

template <typename T, typename = typename std::enable_if<
                          std::is_integral<T>::value, T>::type>
vector<pair<T, int>> prime_factorize(T n) {
  vector<pair<T, int>> cnts{};
  if (n == 1) {
    return cnts;
  }

  T a = 2;
  while (n >= a * a) {

musou1500

#include <vector>

using std::vector;

template <typename T>
class BIT {
  vector<T> tree_;

 public:
  BIT(int n) : tree_(n, 0) {}

musou1500

template<typename T>
void chmax(T &x, const T &y) {
  x = max(x, y);
}

musou1500

namespace mod {

template<class T, int M>
class MInt;

template<class T, int M>
MInt<T, M> Pow(const MInt<T, M> &base, T exp);

template<class T, int M>

musou1500

template <class M, class N>
common_type_t<M, N> gcd(M a, N b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

template <class M, class N>

musou1500

// requires "UnionFind.cpp"

using Edge = array<int, 3>;
vector<Edge> Kraskal(vector<Edge> &edges, int node_size)
{
  UnionFind uf(node_size);

  // 入力された辺を優先度付きキューへ入れる
  priority_queue<Edge, vector<Edge>, greater<Edge>> edge_q(compare);
  for (auto &e : edges) {

musou1500

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main(int argc, const char *argv[])
{
  // 頂点・辺の数
  int n, m;

musou1500

class UnionFind {
  // unordered_map<int, int> graph_;
  // unordered_map<int, int> sizes_;
  vector<int> graph_;
  vector<int> sizes_;

 public:
  UnionFind(int n) : sizes_(n, 1), graph_(n) {
    for (int i = 0; i < n; ++i) {
      graph_[i] = i;

musou1500

class Dijkstra {
  using QItem = pair<int, int>;

 public:
  vector<int> minDistance(vector<array<int, 3>> &edges, int n, int src) {
    vector<int> costs(n, -1);
    costs[src] = 0;

    // 各ノードの隣接ノードとその距離を初期化
    vector<vector<pair<int, int>>> distances(n);

musou1500

const {strictEqual, deepStrictEqual} = require('assert');
const succ = n => ({succ: n});
const pred = ({succ}) => succ || 0;

const solvePlus = expr => {
  if (expr.lhs === 0) {
    return {
      type: 'P-Zero',
      expr,
      ans: expr.rhs,