Shaun and his friends Sean and Shawn are trapped in a huge branching network of underground tunnels beneath the sands, and they desperately need to find their way out. They notice that there are some amount of rooms connected by tunnels that close after you, so they can only be traversed in one direction. By reading the enscriptions on an ancient wall, they also notice that every has at most ~2~ outgoing tunnels. All rooms that have no outgoing tunnels are exit rooms, and they contain elevators to take Shauns to the surface.

Shaun et al desperately want to find a way out, but they don't want to risk getting trapped by making a wrong move. Luckily, in their previous journies, they found the Uncertotron 1000, which will continue making uniformly random choices at every junction over and over again until it reaches an exit room. Can you calculate what the expected number of steps starting from the starting room ~1~ is before the machine reaches an exit room (i.e. a room with no outgoing tunnels)?

Note that the ancient builders of these tunnels never constructed cycles, or else the tunnels would flood when it rains. As mentioned, each room has at most two outgoing tunnels, and there are no paths with a length of more than ~55~. They moreover want their expected steps value as an exact reduced fraction.

Input

The first line contains two integers ~n\ m~ (~1 \leq n, m \leq 10^5~), the number of rooms and the number of tunnels respectively. The rooms are labelled ~1-n~ and you start at room ~1~.

The next ~m~ lines each contain two integers ~u_i\ v_i~ (~1 \leq u_i < v_i \leq n~), describing a tunnel between the two rooms ~u_i~ and ~v_i~, that can only be traversed in that direction.

These tunnels and rooms are guaranteed to form no cycles, and form a graph with a depth of no more than ~55~. Each room has at most ~2~ outgoing tunnels.

Output

Given that the Uncertotron 1000 starts at room ~1~ and continues to pick uniformly random tunnels to traverse until it reaches a room with no outgoing tunnels (an exit room), output the expected number of tunnels it will need to traverse before stopping. Output it as an exact reduced fraction, i.e. output ~p/q~ where ~p,q~ integers and ~gcd(p,q)=1~.

Example

Input 1

4 3
1 2
1 3
2 4

Output 1

3/2

Here you can see the tunnels and rooms. The exit rooms are marked in red. Here, at node ~1~ we have a ~50%~ chance of going to node ~2~, which gives us a path of ~2~ to the exit, and we have a ~50%~ chance of going down to node ~3~ which is an exit itself (path ~1~). Thus our expected path length is ~\frac{1+2}{2}=\frac{3}{2}~.

Input 2

7 7
1 2
1 7
2 4
2 3
3 6
3 4
4 5

Output 2

17/8

Input 3

7 6
1 2
2 3
3 4
1 5
5 6
6 7

Output 3

3/1

All possible paths are same length.