The graphs are in the DIMACS format. Blow we give the introduction to the DIMACS format for undirected graphs, which are taken and slightly edited from http://dimacs.rutgers.edu/Challenges/.


Introduction

DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) defined a format for undirected graph, which has been used as a standard format for problems in undirected graphs. This format was also chosen for several DIMACS Computational Challenges.


Input Files

An input file contains all the information about an undirected graph. 

In this format, nodes are numbered from 1 up to n edges in the graph. 

Files are assumed to be well-formed and internally consistent: node identifier values are valid, nodes are defined uniquely, exactly m edges are defined, and so forth. 


Comments. Comment lines give human-readable information about the file and are ignored by programs. Comment lines can appear anywhere in the file. Each comment line begins with a lower-case character c.  
c This is an example of a comment line.


Problem line. There is one problem line per input file. The problem line must appear before any node or arc descriptor lines. The problem line has the following format. p FORMAT NODES EDGES

The lower-case character p signifies that this is the problem line. The FORMAT field is for consistency with the previous Challenge, and should contain the word ``edge''. The NODES field contains an integer value specifying n, the number of nodes in the graph. The EDGES field contains an integer value specifying m, the number of edges in the graph. 


Edge Descriptors. There is one edge descriptor line for each edge the graph, each with the following format. Each edge (u,v) appears exactly once in the input file and is not repeated as (u,v). 

e u v

The lower-case character e signifies that this is an edge descriptor line. For an edge (u,v) the fields u and v specify its endpoints.