암과의 싸움

암 퇴치 재단(FCC) 연구진이 화학에서 새로운 발견을 발표했다. 탄소 원자를 다른 탄소 원자와 개수 제한 없이 결합시키는 방법을 찾아냈고, 4가 탄소로 만드는 분자보다 훨씬 복잡한 분자를 만들 수 있다. 재단은 이 방법으로 암 치료에 쓸 새로운 약을 개발할 수 있다고 밝혔다.

지금 재단이 합성할 수 있는 분자는 탄소 원자 사이의 결합이 모두 단일 결합이고 구조에 고리가 없는 것뿐이다. 예를 들어 아래 그림의 (a), (b), (c)는 합성할 수 있지만 (d)는 합성할 수 없다.

열운동 때문에 같은 분자도 여러 형태를 띤다. 이미 있는 결합을 끊지 않고 새로운 결합도 만들지 않으면서 한 분자의 원자를 옮겨서 다른 분자와 모양이 정확히 같아지게 만들 수 있으면 두 분자는 동등하다. 위 그림에서 (a)는 (b)와 동등하지 않지만 (c)와는 동등하다.

두 분자의 구조가 주어질 때 두 분자가 동등한지 판정하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어지고, 파일이 끝나는 곳에서 입력도 끝난다. 각 테스트 케이스의 첫 줄에는 두 분자의 원자 개수 $N$이 주어진다. 원자는 $1$부터 $N$까지의 정수로 구분한다. 이어지는 $2N - 2$개의 줄은 각각 원자 두 개 사이의 결합 하나를 나타낸다. 앞의 $N - 1$개 줄은 첫 번째 분자의 결합이고, 뒤의 $N - 1$개 줄은 두 번째 분자의 결합이다. 각 줄에는 정수 $A$와 $B$가 주어지며, 원자 $A$와 원자 $B$ 사이에 결합이 있다는 뜻이다.

제한

• $2 \le N \le 10^4$
• $1 \le A, B \le N$
• 두 분자 모두 고리가 없고 모든 원자가 하나로 이어져 있다.

테스트 케이스마다 문자 하나로 이루어진 한 줄을 출력한다. 두 분자가 동등하면 S, 동등하지 않으면 N을 출력한다.