Problem C
Green Hackenbush

Sample input 1

Hackenbush is a game played on edges of three colours which all connect to each other or the ground. The edges are all red, green or blue. The first player can hack red and green edges and the second blue and green edges. When a player hacks an edge it is deleted. Any edges that can’t reach the ground are discarded.

The value of a Hackenbush game with only green edges is simply the Grandy-Sprague number of that game.

You are given a position in Green Hackenbush. This is a position in the game Hackenbush where all edges are green (can be chopped by either player).

You need to determine the value of the game. As the game only has green edges this will always be an integral nimber.

Input

The first line contains a two integer $0\le n,m\le {10}^5$, the number of points where the edges meet and the number of edges. The next $m$ lines each describe an edge. Each line contains two integers $-1\le x,y\le n$ with $x,y\ne 0$ which denotes an edge going from point $x$ to point $y$. If $x=-1$ the edge goes from the ground to $y$ and vice versa.

Output

If the value of the game is $\ast k$ then print *k. The value of the game is always of this form.

10 12
-1 1
1 2
1 3
2 4
3 4
4 5
5 6
6 7
5 8
8 9
8 9
9 10

*2

1 6
-1 -1
-1 -1
-1 1
1 1
1 1
1 1

*2