해골 병사

당신은 온라인 전략 게임에서 클랜을 새로 만들었다. 클랜마다 마을이 여러 개 있고, 마을 두 개를 잇는 일방통행 도로가 여러 개 있다. 도로의 양 끝이 같은 마을일 수도 있다. 모든 도로의 길이는 같다. 클랜에서 병력을 생산해 다른 클랜을 공격할 수 있다. 당신이 가장 좋아하는 병력은 폭탄을 안고 달려가 상대 마을의 성벽을 부수는 해골 병사다. 해골 병사는 똑똑하고, 어떻게 움직일지 미리 알 수 없다.

공격은 이렇게 진행된다. 먼저 공격할 클랜을 고르고, 그 클랜의 모든 마을에 해골 병사를 한 명씩 배치하고, 폭탄 타이머로 쓸 양의 실수 $t$를 정한 다음 공격 버튼을 누른다. 그 즉시 각 해골 병사가 상대 마을 하나를 목표로 고르는데, 모든 마을이 정확히 한 해골 병사의 목표가 되도록 고른다. 어떤 해골 병사의 출발 마을과 목표 마을이 같아도 된다. 공격이 진행되는 동안 모든 해골 병사는 멈추지 않고 똑같은 일정한 속도로 달린다. 도로는 정해진 방향으로만 지나가고, 같은 도로를 여러 번 지나가도 된다. 정확히 $t$초가 지나면 폭탄이 한꺼번에 터지고 모든 해골 병사가 폭발한다.

모든 해골 병사가 자기 목표 마을에서 폭발하면 공격이 성공한다. 해골 병사는 아주 똑똑해서, 정확히 $t$초 뒤에 목표 마을에 있게 하는 경로가 있다면 반드시 그 경로를 고른다. 클랜 목록이 주어질 때, 해골 병사가 목표를 어떻게 나눠 갖더라도 공격이 반드시 성공하도록 타이머 값을 정할 수 있는 클랜을 모두 찾아라.

입력에는 클랜 여러 개의 정보가 들어 있다. 각 클랜의 첫 줄에 마을의 수 $n$과 도로의 수 $m$이 주어진다 ($1 \le n \le 50000$, $1 \le m \le 100000$). 마을에는 $1$번부터 $n$번까지 번호가 붙어 있다. 다음 $m$개의 줄에는 각각 공백으로 구분된 정수 $x$와 $y$가 주어지며, $x$번 마을에서 $y$번 마을로 가는 일방통행 도로를 뜻한다. 같은 두 마을을 잇는 도로가 여러 개일 수도 있고, 시작 마을과 끝 마을이 같은 도로가 있을 수도 있다. 입력의 마지막 줄은 0 0이며, 이 줄은 처리하지 않는다.

각 클랜마다 한 줄씩 출력한다. 공격이 반드시 성공하도록 타이머 값 $t$를 정할 수 있으면 Y를, 그렇지 않으면 N을 출력한다.