Card Game

Bajtek and Bitek are world-class players of the card game Magiczne Stwory (Magic Creatures). Tonight they face each other in an epic duel that decides who receives the lifetime title of Grand Master. The rules are unusual. Each player owns n distinct decks. Before the actual match, there is a deck selection phase. Starting with Bajtek, the players take turns discarding one of the opponent's decks. When each player has exactly one deck left, the second and final phase begins. The outcome of this phase depends on neither strategy nor luck. For every possible pair of decks that can reach the final match, the result is already known: a win for Bajtek, a win for Bitek, or a draw. Your task is to determine whether Bajtek has a winning strategy. Bajtek has a winning strategy if he wins the final match when both players discard the opponent's decks optimally. If he does not, check whether he has at least a drawing strategy, that is, whether he can ensure that his rival does not receive the title when both players play optimally.

The first line contains one integer t (1 ≤ t ≤ 20), the number of test cases. Each test case starts with a line containing two integers n and m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000). Here n is the number of decks each player has, and m is the number of deck pairs whose selection for the second phase does not result in a draw. The decks of each player are numbered from 1 to n. Then m lines follow, each in the form a w b (1 ≤ a, b ≤ n, w ∈ {<, >}). If w is <, Bajtek's deck a loses to Bitek's deck b. If w is >, Bajtek's deck a beats Bitek's deck b. Each ordered pair (a, b) appears at most once in a test case. If a pair does not appear at all, the final match between Bajtek's deck a and Bitek's deck b ends in a draw.

For each test case, print one line in the order the test cases appear. Print WYGRANA if Bajtek has a winning strategy, REMIS if he has no winning strategy but has a drawing strategy, and PRZEGRANA otherwise.