일련의 관

광섬유 케이블로 물질을 전송하는 기술이 개발되었다. 이 기술을 만든 회사는 전국의 모든 주도를 잇는 광섬유 망을 이미 갖고 있고, 이 망으로 화물 운송 사업을 시작하려고 한다. "인터넷은 화물을 아무렇게나 쏟아붓는 트럭이 아니라 일련의 관이다"라는 오래된 농담이 뜻밖에 현실이 된 셈이다.

망은 광섬유 가지와 집선기로 이루어진다. 주도마다 집선기가 하나씩 있고, 광섬유 가지 하나는 집선기 두 개를 직접 잇는다. 모든 집선기가 서로 직접 이어져 있지는 않지만 망은 연결되어 있다. 즉 어느 집선기에서 출발해도 가지와 집선기를 차례로 지나 다른 어떤 집선기에나 도달한다.

데이터 통신에서는 가지 하나를 양쪽 방향으로 모두 쓴다. 그런데 새 기술에는 특이한 점이 있다. 어떤 가지로 물질을 한 번 보내고 나면 그 가지는 그 방향을 기억하고, 그 뒤로는 오직 그 방향으로만 물질을 보낼 수 있다. 집선기는 이 방향 기억의 영향을 받지 않는다.

가지마다 방향을 하나씩 정해서 어떤 주도에서 어떤 주도로든 화물을 보낼 수 있는지 판정하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 주도의 수 $N$과 광섬유 가지의 수 $M$이 공백 하나를 사이에 두고 주어진다 ($2 \le N \le 1000$, $1 \le M \le 50000$). 주도에는 1번부터 $N$번까지 번호가 붙어 있다.

이어지는 $M$개의 줄에는 각각 두 정수 $A$와 $B$가 주어진다 ($1 \le A, B \le N$, $A \ne B$). 주도 $A$와 주도 $B$를 직접 잇는 가지가 있다는 뜻이다. 데이터 통신에서 이 가지는 $A$에서 $B$로도, $B$에서 $A$로도 쓸 수 있지만 물질 전송에서는 한 방향으로만 쓸 수 있다. 한 쌍의 주도를 잇는 가지는 많아야 하나이다. 각 테스트 케이스의 망은 연결되어 있다.

입력의 끝은 $N$과 $M$이 모두 0인 줄로 표시한다. 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 한 줄을 출력한다. 조건을 지키면서 모든 주도 쌍 사이로 화물을 보낼 수 있으면 S를, 그럴 수 없으면 N을 출력한다.