Autumn Trip

Time limit1sMemory limit128 MB

Summary

Decide whether an undirected graph contains a simple cycle that visits an even number of vertices.

Level: Hard8 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

With a beautiful autumn spreading out beyond the windows, Jakub and Alicja have decided to go on a trip. They plan to drive to some picturesque village, walk around the area for a while, and then return to the spot where they parked the car. Jakub does not want to disappoint Alicja, so the route of the trip has to be interesting.

A route is interesting when, apart from the starting point, it never passes through the same path or the same village more than once. On top of that, because Jakub is superstitious, the route must pass through an even number of villages.

In other words, given an area made of villages and the paths that connect them, decide whether there is a simple closed route that returns to the village it started from, repeats no village or path along the way, and passes through an even number of villages.

Input

The first line contains two integers: the number of villages $n$ ( $1 \le n \le 100000$ ) and the number of paths $m$ ( $1 \le m \le 200000$ ), separated by a space.

Each of the next $m$ lines describes one path with two distinct integers $u$ and $v$ ( $0 \le u, v < n$ ), meaning there is a path that can be walked in both directions between the village numbered $u$ and the village numbered $v$ . No pair of villages appears more than once in the input.

Output

Print JEST on a single line if an interesting trip through an even number of villages exists, or BRAK otherwise.

Examples2

Example 1
Input
```
4 4
0 1
1 2
2 3
0 3
```
Expected output
```
JEST
```
Example 2
Input
```
3 3
0 1
1 2
0 2
```
Expected output
```
BRAK
```