在晚宴上，主办方为大家提供了
n−1 种不同的寿司，编号1,2,3,\ldots,n-1 ，其中第种寿司的美味度为i+1 。（即寿司的美味度为从2 到n ）现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为
x 的寿司，小 W 品尝的寿司中存在一种美味度为y 的寿司，而x 与y 不互质。现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数
p 取模）。注意一个人可以不吃任何寿司。
n \leq 300,p \leq 10^{10}
班上
2n 个学生分成了n 组，每组两个人。其中1 号和2 号为一组，3 号和4 号为一组，……，2n-1 号和2n 号为一组。每个人决定是否愿意和队友合作，对于第
i 个学生，选择“愿意”会产生c_i 的不满，选择“不愿意”会产生d_i 的不满。如果两名队友都选择“愿意”，那么根据实际情况他们可以合作或者不合作。但是如果有一名队友选择“不愿意”，那么他们只能不合作。
如果一个学生
i 选择了“愿意”但是他的队友选择了“不愿意”，那么他会因为队友产生e_i 的不满。学生中还有
m 个单向的喜欢关系，一个关系形如“A 喜欢B ”。在这样一个关系中，有两种情况（其中i 表示第i 个关系，且保证A 和B 不在同一组）：
- 如果
A 没有和队友合作，且B 选择了“愿意”，A 会有产生a_i 的不满- 如果
A 表决了“不愿意”，但B 成功与队友合作，那么A 会产生b_i 的不满。问所有情况下最小的不满之和是多少。
n \leq 5000,m \leq 10000
做了 NOI2018 归程 学到的东西。
给定一个点编号在
[L,R] 范围内的完全图，边(u,v) 的权值为\mathrm{lcm}(u, v) ，请你求出这张图的最小生成树权值和。
L,R \leq 10^6,R - L \leq 10^5
有一棵
n 个节点的树。其中一个简单路径的集合被称为
k 合法当且仅当：树的每个节点至多属于其中一条路径，且每条路径恰好包含
k 个点。对于
k\in [1,n] ，求出k 合法路径集合的最多路径数 即：设k 合法路径集合为S ，求最大的|S| 。
n \leq 10^5