Escape from the Monster

Imagine Little A's dream as an undirected graph with \(n\) vertices and \(m\) edges. Little A is at vertex \(S\), a monster is at vertex \(B\), and a safehouse is located at vertex \(F\). The monster is chasing Little A. However, since this is his dream, Little A can partially control it: he sets his own speed to \(2\) (i.e. he takes \(0.5\) time units per edge) and the monster's speed to \(3\) (i.e. \(\frac{1}{3}\) time units per edge). Moreover, Little A always follows the unique shortest path from \(S\) to \(F\). If there are multiple shortest paths, he chooses the one with the lexicographically smallest sequence of vertex numbers.

The monster wanders through the graph and will never revisit a vertex it has already visited. In the worst-case scenario the monster moves optimally, meaning that if at any vertex on Little A's path the monster can arrive no later than Little A, then Little A is caught at that moment. Formally, let \(p_0, p_1, \ldots, p_k\) be Little A's path (with \(p_0=S\) and \(p_k=F\)). Little A reaches vertex \(p_i\) at time \(\frac{i}{2}\), while the monster can reach \(p_i\) from \(B\) in at least \(\frac{d(B, p_i)}{3}\) time units. If for some index \(i\) we have \[ \frac{d(B, p_i)}{3} \le \frac{i}{2}, \] then in the worst case Little A is caught at time \(\frac{i}{2}\). Otherwise, Little A reaches the safehouse safely.

Your task is to determine whether, in the worst-case scenario, Little A can safely reach the safehouse. If he can, output safe; otherwise, output the time (in time units) at which he is caught.

inputFormat

The first line contains five integers \(n\), \(m\), \(S\), \(B\), and \(F\) (the number of vertices, the number of edges, the starting vertex of Little A, the starting vertex of the monster, and the safehouse vertex, respectively).

Then \(m\) lines follow, each containing two integers \(u\) and \(v\) indicating that there is an undirected edge between vertices \(u\) and \(v\).

outputFormat

If Little A can safely reach the safehouse in the worst-case scenario, output safe. Otherwise, output the time (a number, which may be fractional) at which he is caught.

sample

3 2 1 1 3
1 2
2 3

0