Codeforces 916 C. Jamie and Interesting Graph （构造）

Codeforces 916 C. Jamie and Interesting Graph （构造）

Description

Jamie has recently found undirected weighted graphs with the following properties very interesting:The graph is connected and contains exactly n vertices and m edges.All edge weights are integers and are in range [1, 10^9] inclusive.The length of shortest path from 1 to n is a prime number.The sum of edges’ weights in the minimum spanning tree (MST) of the graph is a prime number.The graph contains no loops or multi-edges.If you are not familiar with some terms from the statement you can find definitions of them in notes section.Help Jamie construct any graph with given number of vertices and edges that is interesting!

Input

First line of input contains 2 integers n, m (2≤n≤105,n−1≤m≤min(n(n−1)2,105))

Output

In the first line output 2 integers sp, mstw (1 ≤ sp, mstw ≤ 10^14) — the length of the shortest path and the sum of edges’ weights in the minimum spanning tree.In the next m lines output the edges of the graph. In each line output 3 integers u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^9) describing the edge connecting u and v and having weight w.

Examples input

4 4

Examples output

7 71 2 32 3 23 4 22 4 4

题意

构造一张包含 n 个点， m 条边的简单图，使得从 1 -> n 的最短路径以及图的最小生成树边权和都为素数。

思路

我们可以构造图的最小生成树为一条链，即 1 -> 2 -> 3 … -> n，在链中有 n-2 条边权值为 1，而另一条边刚好补充使得整个边权和为一个素数。

此外，对于剩余的边就可以随意连接了，只需保证它不会破坏我们之前所构造的 MST 即可。

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef __int64 LL;const int maxn = 3e5+10;int n,m;const int prime = 1e5+3;int main(){ IO; cin>>n>>m; int last = m - n + 1; cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。