FROGS - Frog Wrestling

Billy Jean loves collecting frogs.  Recently, she developed the sport of frog wrestling.  Now she wants to rank her frogs by their wrestling prowess.

Billy Jean has made an algorithm for sorting her frogs.

  1. She arranges N cages, numbered 1,2,...N, each with one frog.
  2. For each pair of cages in a specified, pre-determined list of K pairs of cages,
    1. she removes the frogs from the two cages,
    2. has the frogs wrestle,
    3. puts the winner in the higher-numbered cage, and
    4. puts the loser in the lower-numbered cage.

When she is finished, she hopes to have all her frogs sorted from worst to best in the cages 1 to N.  Will her algorithm work regardless of the initial order of the frogs?

Note:

  • Assume that a strict ordering by wrestling ability is possible.
  • Billy Jean isn't the sharpest tool in the shed.  Sometimes she has written the same two numbers for a pair.  In this case, that frog is simply taken out and then put back.

Constraints

1<=N<=20

1<=K<=1000

Input

The first line is the number of test cases.  Each test cases is preceded by a blank line.

The first line of each test case is N.  The next line is K.  The next K lines are the pairs, separated by a single space.

Output

On separate lines, output whether Billy Jean's algorithm is correct.  Output "YES" (without quotes) if it is or "NO" (without quotes) if it is not.

Example

Input:
4

2
1
2 1

2
1
1 1

1
1
1 1

4
5
1 2
3 4
1 3
2 4
2 3

Output: YES
NO
YES
YES

Added by:Paul Draper
Date:2009-06-24
Time limit:1s-1.735s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2009-07-02 17:08:24 Eigenray
Okay, O(k 2^n) passes.

On the one hand, if you don't know how large k*2^n will be, you won't know if your code will run in time. But on the other hand, if you do know how large it is, it almost gives away the solution, since there's really only one reasonable thing you can do k*2^n times :)
2009-07-02 13:25:49 Paul Draper
Complexity O(2^n*k) should work (but NOT O(n!*k)).

Maximum{ (sum of 2^n*k)/(seconds limit) } = 1.5E8.

Worst case (high K and N) is not present.
2009-06-25 17:51:35 Eigenray
Can you tell us, what is the maximum of (sum of 2^n*k)/(time limit) over all input files?

n=20,k=1000 worst case takes me ~9s spoj time.
2009-06-25 15:24:53 Robert Gerbicz
For n=20,k=1000 that would be TLE.

I've tried lots of random permutations for each input but this is giving WA (->so random not works), or TLE if I'm trying too many sequences.
2009-06-25 13:09:44 [Trichromatic] XilinX
I think, an algorithm with complexity O(2^n * k) can't pass. But this is the only RIGHT algorithm I can think of...

Edit: Seems test data is not strong enough...

Last edit: 2009-07-03 11:38:01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.