도로 네트워크

면접 대비

시간 제한1초메모리 제한2048 MB

요약

도시 N개에서 i번 도로가 도시 i와 (3i+7) mod N을 잇을 때, 모든 도시가 연결되어 있는지 판별하고 연결되지 않으면 서로 이동할 수 없는 도시 두 곳을 찾습니다.

난이도: 쉬움10점 중 3점
유형: 유니온 파인드, 그래프
정답자: 아직 제출이 없습니다

문제

포토코랜드에는 도시가 $N$ 개, 양방향 도로가 $N$ 개 있다. 도시는 0부터 $N-1$ 까지 번호가 붙어 있고, 도로도 같은 방식으로 0부터 $N-1$ 까지 번호가 붙어 있다. 도로 $i$ 는 도시 $i$ 와 도시 $(3 \cdot i + 7) \bmod N$ 을 잇는다. 여기서 $x \bmod N$ 은 $x$ 를 $N$ 으로 나눈 나머지이다. 도로를 따라 어느 도시에서든 다른 모든 도시로 이동할 수 있는지 판단하라. 이동할 수 없다면 서로 연결되어 있지 않은 도시 한 쌍을 찾아라.

입력

첫 줄에 포토코랜드의 도시 수 $N$ ( $1 \le N \le 10^6$ )이 주어진다.

출력

어느 도시에서든 다른 모든 도시로 이동할 수 있으면 YES를 출력한다. 그렇지 않으면 첫 줄에 NO를 출력한다. 둘째 줄에는 도로로 $A$ 에서 $B$ 로 이동할 수 없는 도시 $A$ 와 $B$ ( $0 \le A, B \le N-1$ ; $A \ne B$ )를 출력한다. 답이 여러 개이면 그중 아무거나 하나를 출력한다.

예제2

예제 1
입력
```
4
```
예상 출력
```
NO
0 1
```
예제 2
입력
```
6
```
예상 출력
```
YES
```