1. Write a C program that uses the pebble game technique to test if an input graph is minimally rigid (in two dimensions).

The first line of the input will be n, the number of vertices. n will not exceed 100. Each of the remaining 2n 3 lines will contain two values in the range 0 . . . n 1 to designate an undirected edge. (Self-loops and parallel edges will not be included.) Each input line should be echoed to the output before being processed. The last line of your output should be either 1) an indication that the graph is minimally rigid (Laman) or 2) an indication that the last edge processed is redundant along with the set of vertices giving the rigid subgraph for the redundant edge.

2. If a pebble is moved, you should output the vertices on the path that the pebble is moved along.

3. The input is easily read by using scanf(). Do not prompt for a file name!

4. Your solution must take O(n^2) time, so no adjacency matrices.