URI Online Judge | 3009

Dominos

By Paulo E. D. Pinto, Universidade do Estado do Rio de Janeiro BR Brazil

Timelimit: 3

Kids love to play knocking down rows of dominoes tiles. This is a very fun thing. Many adults also like playing with dominoes. There are huge installations where, from the push of a single tile, there is a sequence of falls from the others. In this problem, you will work with such an installation and must tell if there are any single tile that, if manually pushed, will knock down all tiles of the installation.

Input

The input consists of many tests. The first line contains the number of test cases, an integer      c (1 ≤ c ≤ 20),  Next come  c test cases. Each test case starts with a line containing two integers, n, m (1 ≤ n ≤  1000, 1 ≤  m ≤ 100000), where n indicates the number of pieces and m indicates the number of pairs of pieces, such that if the first is if dropped, it drops also the second.  Follow m lines indicating pairs x and y (1 ≤ x, y ≤ n) of tiles such that x drops y.

Output

For each test case print ‘S’ if there is a single tile that, if manually pushed, will drop all tiles of the installation. Otherwise, print ‘N’.

Input Sample Output Sample

2

3 2

1 3

2 3

5 5

1 2

2 3

3 5

5 2

3 4

N

S