Problem: Bearland has n cities, numbered 1 through n. There are m bidirectional roads. The i-th road connects two distinct cities ai and bi. No two roads connect the same pair of cities. It's possible to get from any city to any other city (using one or more roads).

The distance between cities a and b is defined as the minimum number of roads used to travel between a and b.

Limak is a grizzly bear. He is a criminal and your task is to catch him, or at least to try to catch him. You have only two days (today and tomorrow) and after that Limak is going to hide forever.

Your main weapon is BCD (Bear Criminal Detector). Where you are in some city, you can use BCD and it tells you the distance between you and a city where Limak currently is. Unfortunately, BCD can be used only once a day.

You don't know much about Limak's current location. You assume that he is in one of n cities, chosen uniformly at random (each city with probability <image>). You decided for the following plan:

  1. Choose one city and use BCD there. 
    * After using BCD you can try to catch Limak (but maybe it isn't a good idea). In this case you choose one city and check it. You win if Limak is there. Otherwise, Limak becomes more careful and you will never catch him (you loose). 
  2. Wait 24 hours to use BCD again. You know that Limak will change his location during that time. In detail, he will choose uniformly at random one of roads from his initial city, and he will use the chosen road, going to some other city. 
  3. Tomorrow, you will again choose one city and use BCD there. 
  4. Finally, you will try to catch Limak. You will choose one city and check it. You will win if Limak is there, and loose otherwise. 



Each time when you choose one of cities, you can choose any of n cities. Let's say it isn't a problem for you to quickly get somewhere.

What is the probability of finding Limak, if you behave optimally?

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 400, <image>) — the number of cities and the number of roads, respectively.

Then, m lines follow. The i-th of them contains two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — cities connected by the i-th road.

No two roads connect the same pair of cities. It's possible to get from any city to any other city.

Output

Print one real number — the probability of finding Limak, if you behave optimally. Your answer will be considered correct if its absolute error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if |a - b| ≤ 10 - 6.

Examples

Input

3 3
1 2
1 3
2 3


Output

0.833333333333


Input

5 4
1 2
3 1
5 1
1 4


Output

1.000000000000


Input

4 4
1 2
1 3
2 3
1 4


Output

0.916666666667


Input

5 5
1 2
2 3
3 4
4 5
1 5


Output

0.900000000000

Note

In the first sample test, there are three cities and there is a road between every pair of cities. Let's analyze one of optimal scenarios.

  1. Use BCD in city 1. 
    * With probability <image> Limak is in this city and BCD tells you that the distance is 0. You should try to catch him now and you win for sure. 
    * With probability <image> the distance is 1 because Limak is in city 2 or city 3. In this case you should wait for the second day. 
  2. You wait and Limak moves to some other city. 
    * There is probability <image> that Limak was in city 2 and then went to city 3. 
    * <image> that he went from 2 to 1. 
    * <image> that he went from 3 to 2. 
    * <image> that he went from 3 to 1. 
  3. Use BCD again in city 1 (though it's allowed to use it in some other city). 
    * If the distance is 0 then you're sure Limak is in this city (you win). 
    * If the distance is 1 then Limak is in city 2 or city 3. Then you should guess that he is in city 2 (guessing city 3 would be fine too). 



You loose only if Limak was in city 2 first and then he moved to city 3. The probability of loosing is <image>. The answer is <image>.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            final int inf = 1000;
            int n, m;
            int[][] dist;
            IntArrayList[] gr;

            n = in.readInt();
            m = in.readInt();
//        n = 400;

            dist = new int[n][n];
            ArrayUtils.fill(dist, inf);
            gr = new IntArrayList[n];
            for (int v = 0; v < n; v++) {
                dist[v][v] = 0;
                gr[v] = new IntArrayList();
            }

            for (int iter = 0; iter < m; iter++) {
                int a = in.readInt() - 1;
                int b = in.readInt() - 1;
                dist[a][b] = dist[b][a] = 1;
                gr[a].add(b);
                gr[b].add(a);
            }

//        for (int a = 0; a < n; a++) {
//            for (int b = a + 1; b < n; b++) {
//                dist[a][b] = dist[b][a] = 1;
//                gr[a].add(b);
//                gr[b].add(a);
//            }
//        }

            for (int k = 0; k < n; k++) {
                for (int v = 0; v < n; v++) {
                    for (int to = 0; to < n; to++) {
                        dist[v][to] = Math.min(dist[v][to], dist[v][k] + dist[k][to]);
                    }
                }
            }

            boolean[] used = new boolean[n];
            IntArrayList citiesBear0 = new IntArrayList(n);
            IntArrayList citiesBear1 = new IntArrayList(n);

            double dp = 0;
            for (int v0 = 0; v0 < n; v0++) {
                double dp_V0 = 0;
                for (int d0 = 0; d0 < n; d0++) {

                    while (0 < citiesBear0.size()) {
                        citiesBear0.popLast();
                    }
                    while (0 < citiesBear1.size()) {
                        citiesBear1.popLast();
                    }
                    Arrays.fill(used, false);

                    for (int cityBear0 = 0; cityBear0 < n; cityBear0++) {
                        if (dist[v0][cityBear0] == d0) {
                            citiesBear0.add(cityBear0);
                            for (int cityBear1 : gr[cityBear0]) {
                                if (!used[cityBear1]) {
                                    used[cityBear1] = true;
                                    citiesBear1.add(cityBear1);
                                }
                            }
                        }
                    }

                    if (citiesBear0.size() == 0) {
                        continue;
                    }

                    double dp_V0_D0 = 0;
                    double coef = 1. / citiesBear0.size();
                    if (d0 != 0) {
                        double[] probV = new double[n];
                        for (int b0 : citiesBear0) {
                            double invSize = 1. / gr[b0].size();
                            for (int b1 : gr[b0]) {
                                probV[b1] += coef * invSize;
                            }
                        }


                        double[] probD = new double[n];
                        for (int v1 = 0; v1 < n; v1++) {
                            int[] dist_v1 = dist[v1];
//                    for (int b1 : citiesBear1) {
                            for (int i = 0, imax = citiesBear1.size(); i < imax; i++) {
                                int b1 = citiesBear1.get(i);
                                int d1 = dist_v1[b1];
                                probD[d1] = max(probD[d1], probV[b1]);
                            }
                            double dp_V0_D0_V1 = 0;
//                        for (int b1 : citiesBear1) {
                            for (int i = 0, imax = citiesBear1.size(); i < imax; i++) {
                                int b1 = citiesBear1.get(i);
                                int d1 = dist_v1[b1];
                                dp_V0_D0_V1 += probD[d1];
                                probD[d1] = 0;
                            }
                            dp_V0_D0 = max(dp_V0_D0, dp_V0_D0_V1);
                        }
                    }
                    dp_V0_D0 = max(dp_V0_D0, coef);

                    dp_V0 += ((double) citiesBear0.size() / n) * dp_V0_D0;
                }
                dp = max(dp, dp_V0);
            }
            out.printFormat("%.12f", dp);
            out.printLine();
        }

        private double max(double a, double b) {
            return a < b ? b : a;
        }

    }

    static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
        public IntIterator intIterator();

        default public Iterator<Integer> iterator() {
            return new Iterator<Integer>() {
                private IntIterator it = intIterator();

                public boolean hasNext() {
                    return it.isValid();
                }

                public Integer next() {
                    int result = it.value();
                    it.advance();
                    return result;
                }
            };
        }

        default public int compareTo(IntStream c) {
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                int i = it.value();
                int j = jt.value();
                if (i < j) {
                    return -1;
                } else if (i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if (it.isValid()) {
                return 1;
            }
            if (jt.isValid()) {
                return -1;
            }
            return 0;
        }

    }

    static interface IntCollection extends IntStream {
        public int size();

        default public void add(int value) {
            throw new UnsupportedOperationException();
        }

        default public IntCollection addAll(IntStream values) {
            for (IntIterator it = values.intIterator(); it.isValid(); it.advance()) {
                add(it.value());
            }
            return this;
        }

    }

    static class IntArrayList extends IntAbstractStream implements IntList {
        private int size;
        private int[] data;

        public IntArrayList() {
            this(3);
        }

        public IntArrayList(int capacity) {
            data = new int[capacity];
        }

        public IntArrayList(IntCollection c) {
            this(c.size());
            addAll(c);
        }

        public IntArrayList(IntStream c) {
            this();
            if (c instanceof IntCollection) {
                ensureCapacity(((IntCollection) c).size());
            }
            addAll(c);
        }

        public IntArrayList(IntArrayList c) {
            size = c.size();
            data = c.data.clone();
        }

        public IntArrayList(int[] arr) {
            size = arr.length;
            data = arr.clone();
        }

        public int size() {
            return size;
        }

        public int get(int at) {
            if (at >= size) {
                throw new IndexOutOfBoundsException("at = " + at + ", size = " + size);
            }
            return data[at];
        }

        private void ensureCapacity(int capacity) {
            if (data.length >= capacity) {
                return;
            }
            capacity = Math.max(2 * data.length, capacity);
            data = Arrays.copyOf(data, capacity);
        }

        public void addAt(int index, int value) {
            ensureCapacity(size + 1);
            if (index > size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size) {
                System.arraycopy(data, index, data, index + 1, size - index);
            }
            data[index] = value;
            size++;
        }

        public void removeAt(int index) {
            if (index >= size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size - 1) {
                System.arraycopy(data, index + 1, data, index, size - index - 1);
            }
            size--;
        }

    }

    static interface IntReversableCollection extends IntCollection {
    }

    static interface IntList extends IntReversableCollection {
        public abstract int get(int index);

        public abstract void addAt(int index, int value);

        public abstract void removeAt(int index);

        default public IntIterator intIterator() {
            return new IntIterator() {
                private int at;
                private boolean removed;

                public int value() {
                    if (removed) {
                        throw new IllegalStateException();
                    }
                    return get(at);
                }

                public boolean advance() {
                    at++;
                    removed = false;
                    return isValid();
                }

                public boolean isValid() {
                    return !removed && at < size();
                }

                public void remove() {
                    removeAt(at);
                    at--;
                    removed = true;
                }
            };
        }


        default public void add(int value) {
            addAt(size(), value);
        }

        default public void popLast() {
            removeAt(size() - 1);
        }

    }

    static class ArrayUtils {
        public static void fill(int[][] array, int value) {
            for (int[] row : array) {
                Arrays.fill(row, value);
            }
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void printLine() {
            writer.println();
        }

        public void printFormat(String format, Object... objects) {
            writer.printf(format, objects);
        }

        public void close() {
            writer.close();
        }

    }

    static abstract class IntAbstractStream implements IntStream {

        public String toString() {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                if (first) {
                    first = false;
                } else {
                    builder.append(' ');
                }
                builder.append(it.value());
            }
            return builder.toString();
        }


        public boolean equals(Object o) {
            if (!(o instanceof IntStream)) {
                return false;
            }
            IntStream c = (IntStream) o;
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                if (it.value() != jt.value()) {
                    return false;
                }
                it.advance();
                jt.advance();
            }
            return !it.isValid() && !jt.isValid();
        }


        public int hashCode() {
            int result = 0;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                result *= 31;
                result += it.value();
            }
            return result;
        }

    }

    static interface IntIterator {
        public int value() throws NoSuchElementException;

        public boolean advance();

        public boolean isValid();

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}