bee 3009 - Dominos

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

Input Sample

Output Sample

3 2

1 3

2 3

5 5

1 2

2 3

3 5

5 2

3 4