import java.util.*;
import java.io.*;
import java.security.SecureRandom;
class Graph {
int numNodes;
int numEdges;
int[] nodes;
List<AbstractMap.SimpleEntry<Integer, Integer>> edges;
Graph(int[] nodes, List<AbstractMap.SimpleEntry<Integer, Integer>> edges) {
this.nodes = nodes;
this.edges = edges;
this.numNodes = nodes.length;
this.numEdges = edges.size();
}
}
public class generator {
private final int GRAPH_MIN_NODE_SIZE = 800;
private final int GRAPH_MAX_NODE_SIZE = 2000;
private final int GRAPH_MIN_EDGE_SIZE = 2000;
private final int GRAPH_MAX_EDGE_SIZE = 12000;
private final int PATTERN_MIN_NODE_SIZE = 10;
private final int PATTERN_MAX_NODE_SIZE = 50;
private final int PATTERN_MIN_EDGE_SIZE = 9;
private final int PATTERN_MAX_EDGE_SIZE = 250;
private final int MIN_PATTERN_NUMBER = 25000;
private final int MAX_PATTERN_NUMBER = 50000;
private final int NODE_LABEL_MAX = 10;
private final int HOT_LABELS_MIN = 3;
private final int HOT_LABELS_MAX = 5;
private final double HOT_LABELS_RATIO = 0.8;
private final double SUBGRAPH_RATIO_MIN = 0.3;
private final double SUBGRAPH_RATIO_MAX = 0.7;
private Graph G;
private Graph[] S;
private Random random;
private int randomIntBetween(int lower, int upper) {
return lower + random.nextInt(upper - lower + 1);
}
private double randomDoubleBetween(double lower, double upper) {
return lower + random.nextDouble() * (upper - lower);
}
private int randomElement(int[] array){
return array[randomIntBetween(0, array.length - 1)];
}
private AbstractMap.SimpleEntry<Integer, Integer> randomElement(ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> array){
return array.get(randomIntBetween(0, array.size() - 1));
}
private int randomElement(List<Integer> array){
return array.get(randomIntBetween(0, array.size() - 1));
}
private Graph generateGraph(int minNodes, int maxNodes, int minEdges, int maxEdges) {
int numNodes = randomIntBetween(minNodes, maxNodes);
minEdges = Math.max(minEdges, numNodes - 1);
maxEdges = Math.min(maxEdges, numNodes * (numNodes - 1) / 2);
int numEdges = randomIntBetween(minEdges, maxEdges);
return new Graph(generateNodes(numNodes), generateEdges(numNodes, numEdges));
}
private int[] generateNodes(int numNodes) {
int hotLabelsNumber = randomIntBetween(HOT_LABELS_MIN, HOT_LABELS_MAX);
Integer[] labels = new Integer[NODE_LABEL_MAX];
for (int i = 0; i < NODE_LABEL_MAX; i++) {
labels[i] = i + 1;
}
List<Integer> shuffled = Arrays.asList(labels);
Collections.shuffle(shuffled, random);
shuffled.toArray(labels);
int[] hotLabels = new int[hotLabelsNumber];
int[] coldLabels = new int[NODE_LABEL_MAX - hotLabelsNumber];
for (int i = 0; i < NODE_LABEL_MAX; i++) {
if (i < hotLabelsNumber) hotLabels[i] = labels[i];
else coldLabels[i - hotLabelsNumber] = labels[i];
}
int[] nodeLabels = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
if (randomDoubleBetween(0, 1) < HOT_LABELS_RATIO) nodeLabels[i] = randomElement(hotLabels);
else nodeLabels[i] = randomElement(coldLabels);
}
return nodeLabels;
}
private List<AbstractMap.SimpleEntry<Integer, Integer>> generateEdges(int numNodes, int numEdges) {
Set<AbstractMap.SimpleEntry<Integer, Integer>> edges = new HashSet<AbstractMap.SimpleEntry<Integer, Integer>>();
List<Integer> connectedNodes = new ArrayList<Integer>();
List<Integer> unconnectedNodes = new ArrayList<Integer>();
for (int i = 0; i < numNodes; i++){
unconnectedNodes.add(i);
}
connectedNodes.add(randomElement(unconnectedNodes));
unconnectedNodes.remove(connectedNodes.get(0));
while(unconnectedNodes.size() > 0){
int node1 = randomElement(connectedNodes);
int node2 = randomElement(unconnectedNodes);
int small = Math.min(node1, node2);
int large = Math.max(node1, node2);
edges.add(new AbstractMap.SimpleEntry<Integer, Integer>(small, large));
connectedNodes.add(node2);
unconnectedNodes.remove(Integer.valueOf(node2));
}
ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> unused_edges = new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>();
for (Integer e1 = 0; e1 < numNodes; ++e1){
for (Integer e2 = e1+1; e2 < numNodes; ++e2){
if (!edges.contains(new AbstractMap.SimpleEntry<Integer, Integer>(e1, e2))){
unused_edges.add(new AbstractMap.SimpleEntry<Integer, Integer>(e1, e2));
}
}
}
Collections.shuffle(unused_edges, random);
int pos = 0;
while(edges.size() < numEdges){
AbstractMap.SimpleEntry<Integer, Integer> edge = unused_edges.get(pos);
pos++;
edges.add(edge);
}
return new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>(edges);
}
private Graph generateSubgraph(Graph g){
int numNodes = randomIntBetween(PATTERN_MIN_NODE_SIZE, Math.min(g.numNodes, PATTERN_MAX_NODE_SIZE));
List<List<Integer>> fullEdges = new ArrayList<List<Integer>>();
for (int i = 0; i < g.numNodes; i++){
fullEdges.add(new ArrayList<Integer>());
}
for (AbstractMap.SimpleEntry<Integer, Integer> edge : g.edges){
int node1 = edge.getKey();
int node2 = edge.getValue();
fullEdges.get(node1).add(node2);
fullEdges.get(node2).add(node1);
}
Set<AbstractMap.SimpleEntry<Integer, Integer>> edges = new HashSet<AbstractMap.SimpleEntry<Integer, Integer>>();
int startNode = randomIntBetween(0, g.numNodes - 1);
List<Integer> connectedNodes = new ArrayList<Integer>();
connectedNodes.add(startNode);
ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> boundary_edges = new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>();
for (Integer connected_node : connectedNodes) {
for (Integer neighbor : fullEdges.get(connected_node)) {
if (!connectedNodes.contains(neighbor)) {
boundary_edges.add(new AbstractMap.SimpleEntry<Integer, Integer>(connected_node, neighbor));
}
}
}
while(connectedNodes.size() < numNodes){
AbstractMap.SimpleEntry<Integer, Integer> boundary_edge = randomElement(boundary_edges);
int connected_node = boundary_edge.getKey();
int disconnected_node = boundary_edge.getValue();
int small = Math.min(disconnected_node, connected_node);
int large = Math.max(disconnected_node, connected_node);
edges.add(new AbstractMap.SimpleEntry<Integer, Integer>(small, large));
connectedNodes.add(disconnected_node);
for (Integer neighbor : fullEdges.get(disconnected_node)) {
AbstractMap.SimpleEntry<Integer, Integer> new_edge = new AbstractMap.SimpleEntry<Integer, Integer>(disconnected_node, neighbor);
AbstractMap.SimpleEntry<Integer, Integer> old_edge = new AbstractMap.SimpleEntry<Integer, Integer>(neighbor, disconnected_node);
if (connectedNodes.contains(neighbor)) {
boundary_edges.remove(old_edge);
} else {
boundary_edges.add(new_edge);
}
}
}
int possibleEdges = 0;
for (Integer connected_node : connectedNodes){
for (Integer neighbor : fullEdges.get(connected_node)){
if (connectedNodes.contains(neighbor)) {
possibleEdges++;
}
}
}
possibleEdges /= 2;
int minEdges = Math.max(PATTERN_MIN_EDGE_SIZE, numNodes - 1);
int maxEdges = Math.min(
PATTERN_MAX_EDGE_SIZE,
Math.min(possibleEdges, numNodes * (numNodes - 1) / 2));
int numEdges = randomIntBetween(minEdges, maxEdges);
ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> unused_edges = new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>();
for (Integer connected_node: connectedNodes){
for (Integer neighbor: fullEdges.get(connected_node)){
if (!connectedNodes.contains(neighbor)) continue;
int small = Math.min(connected_node, neighbor);
int large = Math.max(connected_node, neighbor);
if (!edges.contains(new AbstractMap.SimpleEntry<Integer, Integer>(small, large))){
unused_edges.add(new AbstractMap.SimpleEntry<Integer, Integer>(small, large));
}
}
}
Collections.shuffle(unused_edges, random);
int pos = 0;
while(edges.size() < numEdges){
AbstractMap.SimpleEntry<Integer, Integer> edge = unused_edges.get(pos);
pos++;
edges.add(edge);
}
int[] nodes = new int[numNodes];
for (int i = 0; i < numNodes; i++){
nodes[i] = g.nodes[connectedNodes.get(i)];
}
List<AbstractMap.SimpleEntry<Integer, Integer>> ed = new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>(edges);
for (int i = 0; i < ed.size(); i++){
int node1 = ed.get(i).getKey();
int node2 = ed.get(i).getValue();
ed.set(i, new AbstractMap.SimpleEntry<Integer, Integer>(connectedNodes.indexOf(node1), connectedNodes.indexOf(node2)));
}
return new Graph(nodes, ed);
}
private void generate() {
random = new SecureRandom();
G = generateGraph(GRAPH_MIN_NODE_SIZE, GRAPH_MAX_NODE_SIZE, GRAPH_MIN_EDGE_SIZE, GRAPH_MAX_EDGE_SIZE);
double subgraphRatio = randomDoubleBetween(SUBGRAPH_RATIO_MIN, SUBGRAPH_RATIO_MAX);
int numPatterns = randomIntBetween(MIN_PATTERN_NUMBER, MAX_PATTERN_NUMBER);
S = new Graph[numPatterns];
for (int i = 0; i < numPatterns; i++)
{
if (randomDoubleBetween(0, 1) < subgraphRatio) S[i] = generateSubgraph(G);
else S[i] = generateGraph(PATTERN_MIN_NODE_SIZE, PATTERN_MAX_NODE_SIZE, PATTERN_MIN_EDGE_SIZE, PATTERN_MAX_EDGE_SIZE);
}
}
private void printGraph(Graph g, PrintWriter out){
out.println(g.numNodes + " " + g.numEdges);
for (int i = 0; i < g.numNodes; i++){
out.print(g.nodes[i]);
if (i != g.numNodes - 1) out.print(' ');
}
out.println();
for (int i = 0; i < g.numEdges; i++){
out.println((g.edges.get(i).getKey() + 1) + " " + (g.edges.get(i).getValue() + 1));
}
}
private void print() {
PrintWriter out = new PrintWriter(System.out);
printGraph(G, out);
out.println(S.length);
for (int i = 0; i < S.length; i++){
printGraph(S[i], out);
}
out.flush();
}
public static void main(String args[]) {
generator g = new generator();
g.generate();
g.print();
}
}
