A Bug's Life
시간 제한3초메모리 제한256 MB
서로 상호작용한 벌레 쌍이 주어질 때, 같은 성별끼리 상호작용하지 않도록 두 성별을 부여할 수 있는지 판정한다.
문제
호퍼 교수는 희귀한 곤충 종의 짝짓기 행동을 연구하고 있다. 그는 이 곤충에게 서로 다른 두 성별이 있으며, 곤충은 오직 반대 성별의 곤충하고만 상호작용한다고 가정한다. 실험에서는 각 곤충의 등에 번호가 찍혀 있어 개별 곤충과 그들의 상호작용을 쉽게 구별할 수 있었다.
곤충들의 상호작용 목록이 주어질 때, 이 실험이 '성별은 두 개뿐이고 동성 간 상호작용은 없다'는 그의 가정과 모순되지 않는지, 아니면 그 가정을 반증하는 상호작용이 포함되어 있는지 판단하라.
입력
첫 번째 줄에는 시나리오의 개수가 주어진다. 각 시나리오의 첫 번째 줄에는 곤충의 수(1 이상 2000 이하)와 상호작용의 수(1000000 이하)가 하나의 공백으로 구분되어 주어진다. 이어지는 각 줄에는 하나의 상호작용이 서로 다른 두 곤충 번호로, 하나의 공백으로 구분되어 주어진다. 곤충은 1부터 연속해서 번호가 매겨진다.
출력
각 시나리오에 대해 먼저 "Scenario #i:"를 출력한다. 여기서 i는 1부터 시작하는 시나리오 번호이다. 다음 줄에는 실험이 그의 가정과 일치하면 "No suspicious bugs found!"를, 가정이 확실히 틀렸다면 "Suspicious bugs found!"를 출력한다. 서로 다른 시나리오 사이에는 빈 줄을 하나 출력한다.