Road Network

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

요약

각 도시 i를 (3i+7) mod N번 도시와 잇는 N개의 도로가 주어질 때 그래프의 연결 여부를 판정하고, 연결되지 않았다면 서로 갈 수 없는 두 도시를 출력한다.

난이도: 보통10점 중 7점
유형: 그래프, 유니온 파인드, 정수론, 수학
정답자: 아직 제출이 없습니다

문제

There are $N$ cities and $N$ two-way roads in Potokoland. The cities are numbered from $0$ to $N-1$ . The roads are also numbered from $0$ to $N-1$ . The road number $i$ connects cities $i$ and $(3 \cdot i + 7) \bmod N$ , where $x \bmod N$ is the remainder from dividing $x$ by $N$ .

Determine if it is possible to travel from any city to any other city using the roads. If not, find a pair of cities that are not connected.

입력

The first line contains $N$ ( $1 \le N \le 10^6$ ), the number of cities in Potokoland.

출력

Output the word 'YES' if it is possible to travel from any city to any other city.

Otherwise, output the word 'NO' on the first line. On the second line, output any two cities $A$ and $B$ ( $0 \le A, B \le N-1$ ; $A \ne B$ ) such that it is impossible to travel from $A$ to $B$ using the roads. If there are several possible answers, output any one of them.

예제2

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